题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

算法思想一：栈

解题思路：

利用栈的先进后出规则实现链表的翻转

1、首先遍历链表k个结点入栈，若k大于链表的长度则直接返回链表不翻转

2、栈内结点出栈（翻转）

3、判断剩下的链表个数够不够k个（少于k个不需要反转，大于k个重复 1、2步骤）

4、将已翻转的部分与剩下的链表连接起来

图解：

代码展示：

Python版本

class Solution:
    def reverseKGroup(self , head , k ):
        # write code here
        # 用于链表头元素
        Phead = ListNode(None)
        p = Phead
        while True:
            count = k
            stack = []
            tmp = head
            # 进栈
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 跳出上面循环，tmp是第k+1的元素
            # 如果循环结束，count不为0，则代表不足k个元素
            if count:
                p.next = head
                break
            # 对k个元素进行反转
            # 出栈
            while stack:
                p.next = stack.pop()
                p = p.next
            # 与剩下链表链接起来
            p.next = tmp
            head = tmp
        return Phead.next

复杂度分析

时间复杂度O(N)：N表示链表的个数，最差情况下需要遍历所有的链表结点

空间复杂度O(K)：辅助栈最多存储k个结点

算法思想二：递归

解题思路：

1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本***作的尾结点其实就是下一***作的头结点）。
3、对下一轮 k 个节点也进行翻转操作。
4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。

图解：

代码展示：

JAVA版本

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode cur = head;
        int count = 0;
        // 找到待反转的第k个结点
        while (cur != null && count != k) {
            cur = cur.next;
            count++;
        }
        if (count == k) {
            // 递归
            cur = reverseKGroup(cur, k);
            // 反转列表
            while (count != 0) {
                count--;
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            // 拼接后续的链表
            head = cur;
        }
        return head;
    }
}