54.算法->k个一组翻转链表

day6：算法-> 25. K 个一组翻转链表

思路：

• a.先将链表进行分组，然后调用反转链表的方法。参考
• b.利用栈数据结构，先进后出完成反转。

第一种方法

function reverseKGroup(head, k){
  //创建一个目标链表
  let result = new ListNode(0);
  //定义指针
  result.next = head;

  //定义start和end指针
  let pre = result,end = result;
  while(end.next!=null){
     for(let i = 0;i<k&& end!=null;i++) end = end.next;
     if(end == null) break;
    //start指针指向1
     let start = pre.next;
    //end指针指向3
     let temp = end.next;
    //此时链表值只剩下[1,2]
     end.next = null;
     //反转链表
     pre.next = reverseList (start);
    //拼接反转链表
     start.next= temp;
    //重置开始和结束指针
     pre = start;
     end = pre;
  }
  return result.next
}

var reverseList = function (head) {
  let prev = null;
  let curr = head;
  while (curr) {
    //temp保存当前指针的下一个元素
    let temp = curr.next;
    //当前元素的下一个指向prev,前一个元素
    curr.next = prev;
    //再把当前元素赋值给prev
    prev = curr;
    //curr往下移动一位
    curr = temp;
  }
  return prev;
}

第二种方法：

var reverseKGroup = function (head, k) {
  //创建一个目标链表
  let result = new ListNode(0);
  //定义指针
  // result.next = head;
  let p = result;
  //定义一个临时栈
  let tempArr = [];

  while (true) {
    let i = 0;
    for (; i < k && head != null; i++) {
      tempArr.push(head.val);
      head = head.next;
    }
    if (i != k) {
      //拼接后面链表内容
      while (tempArr.length) {
        p.next = new ListNode(tempArr.shift());
        p = p.next;
      }
      break;
    }
    //i=k的时候，此时进行出战操作
    while (i == k && tempArr.length != 0) {
      //
      p.next = new ListNode(tempArr.pop());
      p = p.next;
    }
    //出栈完了之后重新进入,给end重新赋值
  }
  return result.next;
};