Leetcode: 【每日一题】- 2019-08-30 - 链表的分组逆序

[azl397985856]

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）
例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

原文链接： https://www.jianshu.com/p/3dc5e73ab69c

[xiongcaihu]

``` .js
/**

• 思路，
• 进去首先遍历一遍单链表，给每个元素加上preNode属性，表示前置结点，最后用一个变量记录尾结点
  *
• 接下来的循环次数，应该是paseInt(len/K) + len%K
• 分成两段：
• 第一段循环：构造包含K个结点的逆序链表段，并拼接它们
• 第二段循环：构造包含1个结点的逆序连标段，并拼接它们
• 
  
  
  
  • @param {*} head
  
  
• @param {*} K
• @returns
  */
  function reverseLinkedArray(head, K) {
  var len = 0;// 单链表长度
  var nowNode = head,
  preNode = null,
  tailNode = null;
  while (nowNode) {
  nowNode.preNode = preNode;
  preNode = nowNode;
  if (nowNode.next == null) {
  tailNode = nowNode;
  }
  nowNode = nowNode.next;
  len++;
  }

var finalLinkHead = null;
for (var i = 0, count = parseInt(len / K); i < count + (len % K); i++) {
    var j = i >= count ? 1 : K;
    var newHead = new ListNode();
    var tHead = newHead;
    while (j > 0) {
        tHead.val = tailNode.val;
        tHead.next = new ListNode();
        tailNode = tailNode.preNode;
        if (j == 1) {
            break;
        }
        tHead = tHead.next;
        j--;
    }
    tHead.next = finalLinkHead;
    finalLinkHead = newHead;
}

return finalLinkHead;

}

function ListNode(val) {
this.val = null;
this.next = null;
}

function iterateLink(link) {
var array = [];
while (link) {
array.push(link.val);
link = link.next;
}
return array;
}

function demo(array, K) {
var head = new ListNode();
var nowNode = head;
for (var i = 0; i < array.length; i++) {
nowNode.val = array[i];
if (i == array.length - 1) break;
nowNode = nowNode.next = new ListNode();
}

console.log(iterateLink(reverseLinkedArray(head, K)));

}

var timestart = new Date().getTime();
demo([1, 2, 3, 4, 5, 6, 7, 8], 3);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8], 2);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 1);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3);
demo([0, 1], 1);
console.log("use time = ", new Date().getTime() - timestart);
```

[yjua]

function reverse(arr,k){
    var len = arr.length;
    var num = len % k;
    for(var i = num; i< len; i = i+k){
        swap(i);
    }
    function swap(i){
        var temp , begin = i, end = i+k-1;
        while(end - begin > 0){
            temp = arr[begin];
            arr[begin] = arr[end];
            arr[end] =temp;
            begin ++
            end --
        }
    }
    return arr;
}

[azl397985856]

function reverse(arr,k){
  var len = arr.length;
  var num = len % k;
  for(var i = num; i< len; i = i+k){
      swap(i);
  }
  function swap(i){
      var temp , begin = i, end = i+k-1;
      while(end - begin > 0){
          temp = arr[begin];
          arr[begin] = arr[end];
          arr[end] =temp;
          begin ++
          end --
      }
  }
  return arr;
}

是链表，不是数组

[azl397985856]

https://lucifer.ren/blog/2019/09/22/reverseList/