一道编程题——按组翻转链表

题目描述

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

例如：

给定的链表是1→2→3→4→5

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

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

题目分析

这一题难就难在k个一组，并且多余的部分不翻转。

针对于上述的问题，我们需要逐段翻转，翻转之后在正确地连接起来，而剩余部分不翻转。

递归

使用递归方法解决，会比循环容易理解一些。通过递归的返回值将每一段的翻转链表连接起来。

通过设置类成员变量决定递归次数，保证剩余部分不会被翻转。

栈

设置一个长度为 k 的栈，逐个出栈就可以实现翻转，如果栈未满而链表已空则这一段链表不翻转。

代码

python代码

递归实现

class Solution:
    def reverseKGroup(self , head , k ):
        length = 0
        curr = head
        while curr:
            length+=1
            curr = curr.next
        # 建立类成员变量，用来控制递归次数，把链表每k个作为一组（剩余的不分组），每组单独翻转，通过递归使新的组连接在一起
        self.num = length//k
        # 调用递归函数
        root = self.reverseChain(head, k)
        return root
        

    def reverseChain(self, head, k):
        # 递归结束
        if not head: 
            return None
        # 递归次数达到组数
        if self.num ==0:
            return head
        self.num -=1 
        # 翻转链表
        p, c = head, head.next
        i = 1
        while(i!=k and c):
            i+=1
            q = c.next
            c.next = p 
            p = c 
            c = q 
            if q:
                q = q.next
        # 递归，原链表的head节点变成新链表的尾节点，尾节点指向递归返回节点
        head.next = self.reverseChain(c, k)
        return p # 递归函数返回反转之后的链表首节点
    

上述代码，首先遍历链表，计算长度，之后根据长度和k计算出需要翻转的段数，使用一个类成员变量控制类中的递归函数的递归次数。之后就可以调用递归函数了。

递归函数的过程为，遍历链表，每k个节点翻转一次，返回这一段链表反转之后的首节点。而原链表的首节点变成了新链表的尾节点，让这个尾节点指向递归返回值即可。

举个例子：原链表1->2->3->4->5, k=2, 那么翻转后的链表应该是2->1->4->3->5

首先，获取链表长度5，5//2=2即为需要划分的段数，剩余部分不处理。接下来，开始处理链表，此时未处理的链表头节点为1，从1开始取长度为2的链表进行翻转，此时翻转后的链表头节点为2，尾节点为1。递归函数返回节点2，而原链表的头节点即翻转后的尾节点1指向后续链表的递归返回值。

第一次递归后，原始链表变成上述链表，之后继续递归即可。

或者，也可以不使用类成员变量。在遍历链表的过程中确定需要翻转的范围，不满足长度则不翻转。

class Solution2:
    def reverseKGroup(self, head, k):
        if not head:
            return None
        curr = head
        # 找出长度为k的一段链表
        for i in range(k-1):
            curr = curr.next
            # 剩余部分不够k个，直接返回不翻转
            if not curr:
                return head
        # tmp为剩余一段链表的头节点
        tmp = curr.next
        # new_head为翻转后的头节点
        new_head = self.reverse(head, curr)
        # head变成了翻转后的尾节点，则尾节点指向递归后的返回值
        head.next = self.reverseKGroup(tmp, k)
        # 递归返回值为翻转后的头节点
        return new_head

    def reverse(self, head, tail):
        p, c = head, head.next
        while(p!=tail):
            q = c.next
            c.next = p
            p = c
            c = q
        return p

可以使用以下测试代码，测试翻转结果：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 测试
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)

a.next = b
b.next = c
c.next = d


s = Solution2()

new_root = s.reverseKGroup(a, 3)

while new_root:
    print(new_root.val, end='')
    if new_root.next:
        print(' -> ', end='')
    new_root = new_root.next

C++实现

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(!head){
            return NULL;
        }
        ListNode* tail = head;
        for(int i=1; i < k; i++){
            tail = tail -> next;
            if(!tail){
                return head;
            }
        }
        ListNode* next_chain = tail->next;
        ListNode* reversed_head = reverseChain(head, tail);
        head->next = reverseKGroup(next_chain, k);
        return reversed_head;
    }
    
    ListNode* reverseChain(ListNode* head, ListNode* tail){
        ListNode* p = head;
        ListNode* c = head->next;
        ListNode* q;
        while(p!=tail){
            q = c->next;
            c->next = p;
            p = c;
            c = q;
        }
        return p;
    }
};

c++代码的思想与python第二种方法的思想一致，详细见python代码的注释，不再赘述。