K个一组链表进行翻转_k个一组,反转链表

K个一组翻转链表

题目描述：

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解题思路：

当看到这道题的时候，不自觉的让我想起了，翻转链表的那道题目，直接使用头插法，将链表翻转；这道题也应该是同理，我们将给定链表的每一组当做一个单独的链表，然后将其翻转，最后将反转之后的链表进行连接就可以得到结果。那么，实际操作一下吧！

首先我们需要一个逆置链表的算法，很简单使用头插法实现：

ListNode* reverseLink(ListNode* head)
{
    ListNode* pre = head;
    ListNode* cur = NULL;
    
    while(head)
    {
        ListNode* tmp = head->next;
        pre->next = cur;
        cur = pre;
        pre = tmp; 
    }
    
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

得到逆置链表的程序之后，我们就该想想，应该如何去将一个链表分成K组并完成单独的翻转：

1. 首先们需要一个头结点来保存链表的头，避免再反转的过程当中失去了链表的头结点，这样链表也就失去了作用；

2. 根据题目要求，我们可以将链表分为三个部分：已经反转，准备翻转和未翻转；

3. 如何确定准备翻转的链表呢，并且保证链表再反转之后还能与原来的链表连接到一起呢？

   • 首先使用K循环找到我们准备翻转的链表
   • 对我们找到的链表进行翻转，然后与原来的链表相连接
   • 直到找到最后一个节点为止。

   实操一下：

   ListNode* reverseKGroup(ListNode* head,int k)
   {
       ListNode ret;
       ret.next = head;
       ListNode* pre = &ret;
       ListNode* end = &ret;
       //要保证一直找到最后一个节点
       while(end->next != NULL)
       {
           //首先我们需要找到需要翻转的链表
           for(int i = 0; i < k && end != NULL;++i)
           {
               end = end->next;
           }
           //如果end==NULL说明最后剩下的节点不到K个，就不用翻转直接进行连接
           if(end == NULL) break;
           
           //将要翻转的部分和暂时不用翻转的部分分别保存下来，为下一步的连接进行准备
           ListNode* start = pre->next;
           ListNode* next = end->next;
           
           end->next = NULL;
           pre->next = reverseLink(start);
           start->next = next；
           
           //运行到这一步，准备翻转的链表就已经翻转完毕了，然后翻转下一组；
           pre = start;
           end = pre;
       }
       
       return ret.next;
   }
   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

   有人好奇的是我们在进行第一组翻转之后，如何保证反转之后的链表还是和后面的链表保持连接的呢？

   我们在第一步，寻找准备翻转链表的时候，循环完毕end的值应该指向的是准备翻转链表的最后一个节点，此时我们有声明了两个节点，分别是start和next，start保存的是准备翻转链表的头结点，next指向的是end->next，也就是下一组准备翻转链表的头结点，

   重点就是这两个接点，当翻转之后，start成了翻转链表的尾结点，我们让start->next = next；就可以是的翻转之后的链表与原来的链表进行连接了。