139-k个一组反转链表(递归)

末蓝、 2023-01-08 05:27 131阅读 0赞

**题目：**  
将给出的链表中的节点每k 个一组翻转，返回翻转后的链表  
如果链表中的节点数不是k 的倍数，将最后剩下的节点保持原样  
你不能更改节点中的值，只能更改节点本身。

**例如：**

给定的链表是1->2->3->4->5

对于 k=2, 你应该返回 2→1→4→3→5

对于 k=3, 你应该返回 3→2→1→4→5

**本次采用递归的方法解决此问题  
我的解题思路如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
特别注意：  
reverseKGroup(tail,k);//递归入栈操作。

head->next = reverseKGroup(tail,k);  
当前head（还未进行逆置的头结点）指向当前尾 ，当前的尾指的就是已经逆置好的新子链的头结点或者是小于k的不需要逆置的子链的头结点，然后现在的新的子链进行逆置（递归出栈）  
**代码如下**

ListNode* reverseKGroup(ListNode *head, unsigned int k)
    {
        
        if(head == NULL || head->next == NULL)
        {
        
            return head; 
        }
        ListNode *tail = head;
        for (int i = 0; i < k; ++i)
        {
        
            if(tail == NULL)
            {
        
                return head;//小于k，不改变
            }
            tail = tail->next;
        }
        
        ListNode *newHead = reverseList(head, tail);//获取新子链的头结点 
        
        head->next = reverseKGroup(tail,k);//递归入栈，当前head指向当前尾 
        
        return newHead;//递归全部出栈后，最后返回整条新链的头结点 
    }
    
    ListNode* reverseList(ListNode* head, ListNode* tail)//逆置子链 
    {
        
        ListNode *p= NULL,*q= NULL;
        while(head!=tail)
        {
        
            p= head->next;
            head->next=q;
            q=head;
            head=p;
        }
        return q;//返回新子链的头结点 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/82f4bb37ddfb4a7ca9826b418a92fa4d.png