LeetCode 25. K 个一组翻转链（难）

基于链表或者栈、队列，都可以解决这个问题。

题目

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

说明 :
你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

1
2
3
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

考察知识点

链表、利用栈先进后出的特点可以做reverse

核心思想

方法一、基于栈

用栈，我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的！
这里要注意几个问题：
第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；
第二，已经翻转的部分要与剩下链表连接起来。
这个方法，不满足只能使用常数的额外空间的要求，故放弃。

方法二、尾插法

锁定 head、cur、tail三个指针，固定尾部，将cur依次插到tail后面。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pre
tail    head
dummy    1     2     3     4     5
# 我们用tail 移到要翻转的部分最后一个元素
pre     head       tail
dummy    1     2     3     4     5
	       cur
# 我们尾插法的意思就是,依次把cur移到tail后面
pre          tail  head
dummy    2     3    1     4     5
	       cur
# 依次类推
pre     tail      head
dummy    3     2    1     4     5
		cur
....
关键步骤，空出cur。

1
2
3
4
cur = pre.next  # 获取下一个元素 第一个获取的是head.next
pre.next = cur.next  # pre与cur.next连接起来,此时cur(孤单)掉了出来
cur.next = tail.next  # 和剩余的链表连接起来
tail.next = cur  # 插在tail后面

方法三、基于递归的方法

注意把握递归条件

大佬题解

Python版本

基于栈先进后出特点的实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class ListNode():
    def __init__(self, value):
        self.val = value
        self.next = None

    def __str__(self):
        return str(self.val)


def createList(value_list: list) -> ListNode:
    """
    Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return None
    if _len == 1:
        return ListNode(value_list[0])
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            tmp.next = ListNode(value_list[i])  # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp = tmp.next  # 更新tmp
    return root # 返回根节点


def listLength(head: ListNode) -> int:
    """
    Get the length of linked list
    :param head: ListNode
    :return: int
    """
    count = 0
    p = head
    while p != None:
        count += 1
        p = p.next
    return count


def convert2list(head: ListNode) -> list:
    """
    Convert linked list to normal list
    :param head: ListNonde
    :return: list
    """
    res = []
    p = head
    while p != None:
        res.append(p.val)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next
    return res


class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k 
            stack = []  # 直接调用list做stack，list就有pop函数。
            tmp = head
            # 将head之后的k个node（包括head本身）入栈
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个, 跳出循环
            if count: 
                p.next = head
                break
            # 翻转操作
            while stack:
                p.next = stack.pop()
                p = p.next
            head = tmp  # 更新head
        
        return dummy.next


print("leet code accept!!!")
Input = [[1, 2, 3, 4, 5]]
Input1 = [2]
Answer = [[2, 1, 4, 3, 5]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.reverseKGroup(createList(Input[i]), Input1[i])
        print(convert2list(result))
        print(Answer[i])

执行用时 :68 ms, 在所有 Python3 提交中击败了26.14%的用户
内存消耗 :14.3 MB, 在所有 Python3 提交中击败了36.03%的用户

插入法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy  # pre永远是head节点的前驱，用pre来串联处理结果。
        tail = dummy
        while True:
            count = k
            # 将tail移到k个Node之后
            while count and tail:  # 当count没插完，tail非None时。
                count -= 1
                tail = tail.next
            if not tail: break  # 如果tail为空 中断循环
            head = pre.next  # 一开始，pre=dummy dummy.next=head，所以pre.next=head。将head指定在开始位置
            while pre.next != tail:  # 一开始pre.next是head，即从head一直遍历到tail
                cur = pre.next  # 获取下一个元素 第一个获取的是head.next
                pre.next = cur.next  # pre与cur.next连接起来,此时cur(孤单)掉了出来
                cur.next = tail.next  # 和剩余的链表连接起来
                tail.next = cur  # 插在tail后面
            # 改变 pre tail 的值
            pre = head 
            tail = head
        return dummy.next

执行用时 :68 ms, 在所有 Python3 提交中击败了26.14%的用户
内存消耗 :14.3 MB, 在所有 Python3 提交中击败了36.03%的用户

递归方法实现 推荐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # cur：等待被指向
        # head：指向cur，并声明tmp
        # tmp：等待替换head
        cur = head  # 第一次递归 cur从head开始
        count = 0
        while cur and count!= k:
            cur = cur.next
            count += 1
        # 到这个while结束之后，cur变成第k+1个node，下一次递归，cur从k+1个节点开始，而下下次递归，cur从2k+1个节点开始，以此类推。
        if count == k:  # 当count == k时，说明是一次完整的子链表，进行递归。
            cur = self.reverseKGroup(cur, k)  # 将下一层递归翻转后的head节点作为cur
            while count:  # 递归调用之后，由于前面已经判断了count == k，所以一定是一个完整的子链。故而直接翻转。
                tmp = head.next  # 设置tmp为head下一个节点，一会儿要把tmp放到head前面
                head.next = cur  # 这里的cur是下一层递归得到的head，指定head指向cur
                cur = head  # 更新cur，cur永远是处理完了之后的head。
                head = tmp  # 更新head，head变成了tmp，也就是前一个head后面那个节点现在是新的head，这样一来，最终head会变成tail。
                count -= 1  # 处理一次，count减1。
            head = cur # while循环完，代表这层递归结束，此时cur已经移到了原来节点顺序中的最后一位，此时设置cur为head即可。
        # 否则，不进行翻转（题干中已经说明了，不足k个节点的子链可以不做翻转。），然后直接返回head。
        return head

执行用时 :56 ms, 在所有 Python3 提交中击败了54.84%的用户
内存消耗 :14.4 MB, 在所有 Python3 提交中击败了32.63%的用户