Leetcode 25. K 个一组翻转链表

1.题目基本信息

1.1.题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1.2.题目地址

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

2.解题方法

2.1.解题思路

链表反转

2.2.解题步骤

第一步，构建维护变量。dumbNode为哑结点；tail维护新链表的尾部结点；node1和node2维护分段链表的首尾结点（node2可能为None）

第二步，移动结点node1和node2，分段进行翻转，并将翻转后的链表链接到tail上

第三步，返回新链表

3.解题代码

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next# 链表反转函数。
def reverseList(head:ListNode, tail:ListNode) -> (ListNode, ListNode):pre = Nonenode = headwhile node != tail:temp = node.nextnode.next = prepre = nodenode = tempreturn pre, headclass Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:# 第一步，构建维护变量。dumbNode为哑结点；tail维护新链表的尾部结点；node1和node2维护分段链表的首尾结点（node2可能为None）dumbNode = ListNode()tail = dumbNodenode1, node2 = head, head# 第二步，移动结点node1和node2，分段进行翻转，并将翻转后的链表链接到tail上while node2 is not None:for i in range(k):node2 = node2.nextif node2 is None and i != k - 1:tail.next = node1return dumbNode.nextnewHead, newTail = reverseList(node1, node2)tail.next = newHeadtail = newTailnode1 = node2# 第三步，返回新链表return dumbNode.next

4.执行结果