LeetCode链表之 K 个一组翻转链表_翻转指针k

题目：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

---

思路：

3步：找到第k个结点--------翻转-------连接到链表中。

从前往后遍历链表，当遇到第k个结点，进行翻转；然后再往后遍历k个结点，进行翻转，重复进行，由此可以用递归来实现。

public ListNode reverseKGroup(ListNode head, int k) {
   if(head == null || head.next == null)return head;//递归结束条件
   ListNode p = head;
   //找到第k个结点
   for(int i = 1;i < k && p != null; i++){//注意：p开始指向head，所以只需移动k-1下；不要忘记p!= null
     p = p.next;
   }
   if(p == null)return head;//如果p==null,说明长度不够k，不用翻转，直接返回
   ListNode pNext = p.next;//记录p的下一个结点,作为下次翻转的头结点，后面翻转会用到
   p.next = null;//这里不能忘掉
   ListNode newHead = reverse(head);//翻转长度为k的链表
   ListNode nextNode = reverseKGroup(pNext,k);//递归翻转后一部分的链表
   head.next = nextNode;//反转后head到链表尾部，让head指向后一部分翻转后的头结点
   return newHead;//返回新的头结点
}

//翻转链表函数
public ListNode reverse(ListNode head){
   if(head == null || head.next == null)return head;//递归结束条件
   ListNode res = reverse(head.next);//递归翻转
   head.next.next = head;//开始翻转
   head.next = null;
   return res;//一层一层向上返回新的头结点res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

进阶：不用额外的空间

思路：

不用额外空间，其实也不是很难。找到第k个结点，翻转，再找第k个结点，翻转…

如图，有5个结点的链表，k = 3时：

1）设置辅助结点dummy，pre，end起始位置如下：

2）从前往后移动k个结点，end指向移动后的结点：
3）翻转k个结点之前先设置2个指针 start 和 pLast，start用来记录翻转后的尾结点，pLast用来记录第k个结点的下一个结点(翻转时从start所指的结点开始反转，即不翻转dummy结点)。翻转前记得将end.next置空。

4）翻转k个结点，各个指针(引用)位置如下：

5）修改指针：先将翻转后的长度为k的链表连接到链表中，并修改pre和end所指结点，以便下次翻转。

上面涉及到了4个引用(指针)，容易混乱，这里再总结下，可以看到：

• end 用来记录翻转前第k个结点；
• pLast 用来记录翻转前第k个结点的下一个结点；
• start 用来记录翻转后的尾结点(翻转前的首结点)，翻转后进行连接要用到；
• pre 用来记录上一次翻转k个结点后的尾结点，此次翻转后连接时，将pre.next指向翻转后的首节点。

参考代码

public ListNode reverseKGroup(ListNode head, int k) {
  if(head == null || head.next == null)return head;
  //创建辅助结点
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  ListNode end = dummy;
  ListNode pre = dummy;//pre指向上次翻转k个结点后的最后一个结点
  //end为null退出循环
  while(end != null){
     //找到第k个结点；//注意：别忘了end != null
     for(int i = 0; i < k && end != null; i++)end = end.next;
     if(end == null)break;//不够k个，不用翻转，直接break
     ListNode pLast = end.next;//指向end的第后一个结点，连接时要用到
     ListNode start = pre.next;//start指向翻转后的尾结点(翻转前个首结点)
     end.next = null;//别忘了将end.next置空
     pre.next = reverse(start);//翻转以start为首结点的长度为k的链表，并用上次翻转后的尾结点pre指向它
     start.next = pLast;//翻转后的链表尾部和pLast结点相连接
     //修改指针
     pre = start;//修改pre，重置为翻转后的尾结点
     end = pre;//end重置为pre，即下一次翻转首结点的前一个结点
  }
  return dummy.next;//返回辅助结点的下一个结点
}

public ListNode reverse(ListNode head){
  if(head == null || head.next == null)return head;
  ListNode pre = null;
  ListNode curr = head;
  ListNode cnext = curr.next;
  while(cnext != null){
    curr.next = pre;
    pre = curr;
    curr = cnext;
    cnext = cnext.next;
  }
  curr.next = pre;
  return curr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

进阶：字节跳动面试题

题目：

给定一个单链表的头节点 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不调整，因为不够一组。

思路：

有了上面的基础，这道题就八九不离十了，上面是从前往后翻转，而这道题是从后往前进行翻转。

例如：

【1，2，3，4，5】，K = 3时，

从后往前翻转，结果为：【1，2，5，4，3】

另外一种思路：

1）翻转链表，结果为：【5，4，3，2，1】；
2）从头到尾每k个结点一翻转，结果为【3，4，5，2，1】；
3）翻转链表，结果为：【1，2，5，4，3】

可以看到，和上面结果一致。

于是可以这样考虑：

1）将整个链表先进行翻转；

2）从头到尾每k个一翻转链表；

3）将整个链表再进行翻转，返回头结点。

可以看到，这道题只是在上道题基础上前后翻转了2次。

参考代码

public ListNode result(ListNode head, int k) {
   if(head == null || head.next == null)return head;
   //翻转整个链表
   head = reverse(head);
   //每隔k个结点翻转操作
   head = reverseKGroup(head,k);
   //翻转整个链表
   head = reverse(head);
   //返回
   return head;
}

public ListNode reverseKGroup(ListNode head, int k) {
   if(head == null || head.next == null)return head;
   ListNode p = head;
   for(int i = 1; i < k && p != null; i++)p = p.next;
   if(p == null)return head;
   ListNode pNext =  p.next;//记录p结点的下一个结点
   p.next = null;//不能忘掉
   ListNode newHead = reverse(head);//翻转
   head.next = reverseKGroup(pNext,k);
   return newHead;
}

public ListNode reverse(ListNode head){
  if(head == null || head.next == null)return head;
  ListNode pre = null;
  ListNode curr = head;
  ListNode nextNode = curr.next;
  while(nextNode != null){
    curr.next = pre;//翻转
    pre = curr;
    curr = nextNode;
    nextNode = nextNode.next;
  }
  curr.next = pre;
  return curr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

小结

在做算法题时，一些细节还是没有想到位，就算多写几次有可能还是忘记，应该多总结。