第 138 题：反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序

[yygmind]

[w1301625107]

我这个是链表尾部开始的，和这个头部开始的差不多

let a = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: {
          value: 5,
          next: {
            value: 6,
            next: {
              value: 7,
              next: {
                value: 8,
                next: {

                }
              }
            }
          }
        }
      }
    }
  }
}

function reverseList(_head, _k) {
 // 这个求长度可以用循环，用递归长链表容易爆栈
  let get_length = (_list) => {
    if (_list == null || _list.next == null) {
      return 0
    }
    return get_length(_list.next) + 1
  }

  let list_length = get_length(_head)

  function jump(_list, _step) {
    let _t = _list
    while (_step-- > 0) {
      _t = _t.next
    }
    return _t
  }


  function reverse(_node, _step) {
    if (_step == 0) {
      return _node
    }
    let _rt = reverse(_node.next, _step - 1)
    _node.next.next = _node
    _node.next = null

    return _rt
  }

  let _count = list_length % _k
  let _link = {
    next: _head
  }
  let _link_postion = jump(_link, _count)
  let _next_start_position = null;
  while (_count < list_length) {
    let _current_start_position = _link_postion.next
    _next_start_position = jump(_link_postion, _k + 1)
    _link_postion.next = reverse(_current_start_position, _k - 1)
    _link_postion = jump(_link_postion, _k)
    _link_postion.next = _next_start_position
    _count = _count + _k;
  }

  return _link.next
}

console.log(reverseList(a, 4))

[feikerwu]

/**
 * 反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序
 */

interface ListItem {
  next: ListItem | null;
  value: any;
}

interface group {
  head: ListItem;
  tail: ListItem;
}

function reverseEveryKItems(head: ListItem, k: number): ListItem {
  let headTmp: ListItem = head;
  let groupHeads: Array<ListItem> = [];
  let count = 1;
  groupHeads.push(headTmp);

  // 对列表分组
  while (headTmp.next) {
    count = count + 1;
    if (count === k) {
      groupHeads.push(headTmp.next);
      count = 0;
    }
    headTmp = headTmp.next;
  }

  let lastGroupHead: ListItem;
  // 不满K个节点的不反转
  if (count !== 0) {
    lastGroupHead = groupHeads.pop();
  }

  // 每K个节点置换，保存head，tail
  const groups: Array<group> = groupHeads.map((groupHead) =>
    reverseGroupList(groupHead, k)
  );

  // 将每个反转后的组前尾后头连起来
  let reverseHead: ListItem = groups[0].head;
  for (let i = 1; i < groups.length; i++) {
    let preTail = groups[i - 1].tail;
    let curHead = groups[i].head;
    preTail.next = curHead;
  }

  groups[-1].tail.next = lastGroupHead || null;

  return reverseHead;
}

/* 每K个列表反转 */
function reverseGroupList(head: ListItem, k: number): group {
  let pre: ListItem = head;
  let cur: ListItem = head.next;

  while (cur && k--) {
    let next: ListItem = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }

  return {
    head: cur,
    tail: head
  };
}

[cchaonie]

大致思路：

• 遍历链表，将每个元素添加到一个栈中
• 判断栈的长度，达到指定长度后，出栈，即可反转
• 若最后一次栈的长度没有达到指定长度，则将这个栈当作队列操作，直接出队

实现如下：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }

  print() {
    let pointer = this;
    let result = '';
    while(pointer) {
      result += pointer.value + '>';
      pointer = pointer.next;
    }
    console.log(result.substring(0, result.length - 1));
  }
}

function reverseLinkedListByk(linkedList, k) {
  if (!linkedList) {
    return null;
  }
  if (k < 1) {
    return linkedList;
  }
  const stack = [];
  let resultHead = null;
  let resultPointer = null;
  let traversePointer = linkedList;
  while(traversePointer) {
    const copy = traversePointer;
    traversePointer = traversePointer.next;
    copy.next = null;
    stack.push(copy);
    if (stack.length == k) {
      while(stack.length) {
        const node = stack.pop();
        if (!resultHead) {
          resultHead = resultPointer = node;
        } else {
          resultPointer.next = node;
          resultPointer = resultPointer.next;
        }
      }
    }
  }
  if (stack.length && stack.length < k) {
    while(stack.length) {
      const node = stack.shift()
      resultPointer.next = node;
      resultPointer = resultPointer.next;
    }
  }
  return resultHead;
}

const linkedList = new Node(5);
n1 = new Node(8);
n2 = new Node(3);
n3 = new Node(6);
n4 = new Node(9);
n5 = new Node(1);
n6 = new Node(10);
n7 = new Node(39);
linkedList.next = n1
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
linkedList.print();
console.log('----------');
let reversed = reverseLinkedListByk(linkedList, 3);
reversed.print();

[HCLQ]

楼上的各位，这题用数组做就没意思了啊
纯链表加索引解决的思路:
拆分为2个函数

1. 只反转链表
2. 在找到需要反转的链表，用 1 去反转
   每一轮循环中，将链表视为
   pre => start => *** => end => next
   我们翻转 start => *** => end 这一段, 变为
   pre end => *** => start next
   再将原链表和翻转后的合并即可，然后寻找下一段要反转的链表继续循环
   pre => end => *** => start => next

// 定义链表节点
class Node {
  constructor(v, last) {
    this.next = null
    this.value = v
    if (last) {
      last.next = this
    }
  }
}

let head = makeList(10)
console.info(toString(head))
head = invert(head, 3)
console.info(toString(head))

// 原链表:  0,1,2,3,4,5,6,7,8,9
// 反转后:  2,1,0,5,4,3,8,7,6,9

// ---- 核心思想 -----
/**
 * 链表每m个节点反转
 * @param {*} head
 * @param {*} n
 */
function invert(head, n) {
  let pre = new Node(999, null)
  pre.next = head
  let start = head
  let end = head
  // 缓存头
  head = pre
  let count = 1
  while (start && end) {
    // 查找需要反转的链表 end 节点
    if (count < n) {
      count++
      end = end.next
    } else {
      count = 1
      // 缓存对 end 之后的链表的索引
      let next = end.next
      // 反转 start -> ** ->  end 这段链表
      revert(start, next)
      // 反转成功后, end 节点是新链表的头了, 而 start 是尾了
      pre.next = end
      // 反转的链表连上剩下的链表
      start.next = next
      // 初始化下一段要反转的链表段
      pre = start
      start = next
      end = next
    }
  }
  return head.next
}

/**
 * 给定一个链表头和结束标记进行反转
 * @param {*} start
 * @param {*} endTag
 */
function revert(start, endTag) {
  let temp
  let pre = null
  while (start !== endTag) {
    temp = start.next
    start.next = pre
    pre = start
    start = temp
  }
  return pre
}

// ----工具-----

// 构造一个链表
function makeList(length) {
  const head = new Node(-1, null)
  Array.from({length}, (_, i) => i).reduce((last, key) => new Node(key, last), head)
  return head.next
}

// 打印链表
function toString(head) {
  let temp = new Node(999, null)
  temp.next = head
  let show = []
  while ((temp = temp.next)) {
    show.push(temp.value)
  }
  return show.join(',')
}

[lhyt]

// 创建链表
function createLinkList(...args) {
  const res = {};
  let current = res;
  while (args.length) {
    current.value = args.shift();
    current.next = {};
    current = current.next;
  }
  return res;
}

function reverse(linklist, k) {
  const stack = [];
  let current = linklist;
  // 前面k个入栈
  while (current.next && stack.length + 1 <= k) {
    stack.push(current.value);
    current = current.next;
  }
  // 不足k不用反转
  if (stack.length < k) {
    return linklist;
  }
  // 出栈+拼接current节点再递归
  let temp = {};
  const ret = stack.reduceRight(
    (res, cur) => ((temp.value = cur), (temp = temp.next = {}), res),
    temp
  );
  current && current.next && Object.assign(temp, reverse(current, k));
  return ret;
}

reverse(createLinkList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), 3);

[hhparty]

糟糕，又是不会的感觉

[HCLQ]

(#`O′)！你们用数组的不觉得很犯规么！

[w1301625107]

(#`O′)！你们用数组的不觉得很犯规么！

我记得看到头条的是说不能用其他的数据结构

[Hi-yulin]

我枯了

[JaniceDong]

看了一楼的解释，我的理解是3-2-1,6-5-4,7-8，三组，难道我理解错了?

[w1301625107]

看了一楼的解释，我的理解是3-2-1,6-5-4,7-8，三组，难道我理解错了?

对啊，但是我写的是网络上头条的给的题目，头条是链表尾部开始，这个题目是表头开始，原理是类似的

[Kisnnnnn]

      class Node {
        constructor(v, last) {
          this.value = v
          this.next = null
        }
      }
      function NodeList() {
        //   容器
        let head = null
        // 长度
        let length = null
        this.append = function(val) {
          let cur,
            node = new Node(val)

          if (head == null) {
            head = node
          } else {
            cur = head
            while (cur.next) {
              cur = cur.next
            }
            cur.next = node
          }
          length++
        }
        this.removeAt = function(pos) {
          let cur = head,
            index = 0,
            prev

          if (pos === 0) {
            let nodes = cur
            head = cur.next
            return nodes
          } else {
            while (cur.next) {
              if (index++ === pos) {
                prev.next = cur.next
                return cur
              }
              prev = cur
              cur = cur.next
            }

            return -1
          }
        }
        this.reverseList = function(k) {
          let res
          if (k >= length) {
            return head
          }
          //   进行轮询节点反转
          for (let i = 0; i < Math.floor(length / k) + 1; i++) {
            let index = 0,
              reverNodes

            // 反转节点
            while (index < k && head) {
              //  拿到删除的节点（永远是第一个）
              let node = nodeList.removeAt(0)
              // 如果本轮节点组为空，则重置本次节点
              if (reverNodes == null) {
                reverNodes = node
                node.next = null
              } else {
                //   拼接节点
                node.next = reverNodes
                reverNodes = node
              }

              index++
            }
            if (res == null) {
              res = reverNodes
            } else {
              let cur = res
              while (cur.next) {
                cur = cur.next
              }

              cur.next = reverNodes
            }
          }
          head = res
          return res
        }
        this.getContent = function() {
          let cur = head,
            res = []

          while (cur) {
            res.push(cur.value)
            cur = cur.next
          }

          console.log(res.join('->'))

          return res.join('->')
        }
      }
      //   实例节点
      let nodeList = new NodeList()
      //   添加节点
      for (let i = 0; i < 20; i++) {
        nodeList.append(i)
      }
      // 反转节点
      nodeList.reverseList(3)
      //   查看内容
      nodeList.getContent()

[yaodongyi]

数组犯规么，好吧那就不用数组，直接递归。

// 反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序
// 构建链表
function list(...val) {
    let obj = val.reverse().map((res, i) => Object.assign({}, { [i]: new Node(res) }));
    for (let item in obj) {
        if (item != 0) obj[item][item].next = obj[Number(item) - 1][Number(item) - 1]
    }
    return obj[obj.length - 1][obj.length - 1];
};
class Node {
    constructor(element) {
        this.value = element;
        this.next = null;
    }
}
// 链表反转
function reverse_linkedList(linkedList) {
    let str = '';
    let fn = function (list) {
        if (n === 1) {
            if (list.next && list.next.next) {
                let value = list.value;
                let endValue = list.next.next.value;
                list.next.next.value = value;
                list.value = endValue;
            }
        }
        str += list.value.toString() + ">"
        if (n === 3) {
            n = 0
        }
        if (list.next === null) {
            return false
        };
        n++
        fn(list.next)
        return str.substring(0, str.length - 1)
    }
    return fn.call(reverse_linkedList, linkedList, n = 1)
}

let linkedList = list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

console.log("原始链表", list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
reverse_linkedList(linkedList); 
console.log("\n反转链表", linkedList);

[HduSy]

reverse
```太复杂了吧，看不懂啊