LeetCode25 k个一组翻转链表

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

LeetCode第25题

问题描述

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明:

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

解题思路

本题是交换链表节点题的延伸。本题解题思路可以采用递归法，先翻转前k个节点(如果链表小于k个节点，直接返回链表)，然后递归对其余节点进行翻转，最后将两者接上。
由于头节点可能会改变，所以在链表头部插入一个空节点。

代码

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        new_head = ListNode(0)
        new_head.next = head
        p = head
        
        node_count = 0
        while node_count < k and p:
            p = p.next
            node_count += 1
        if node_count == k:
	    # 对剩余的节点进行K-组翻转
            current_node = self.reverseKGroup(p, k)
	    # 对本次k节点进行翻转，并接上current_node
            while k > 0:
                temp = new_head.next
                new_head.next = temp.next
                temp.next = current_node
                current_node = temp
                k -= 1
	    # 注意这里需要将空节点指向current_node
            new_head.next = current_node
        
        return new_head.next
相关文章
感谢你对我的支持，让我继续努力分享有用的技术和知识点