K个一组翻转链表（LeetCode）

题目

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

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

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

解题

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseKGroup(head, k):"""翻转链表中每 k 个节点一组的节点。:param head: 链表的头节点:param k: 每组翻转的节点数量:return: 翻转后的链表头节点"""def getKthNode(current, k):"""获取链表中第 k 个节点。:param current: 当前节点:param k: 节点数量:return: 第 k 个节点或 None（如果不足 k 个节点）"""while current and k > 1:current = current.nextk -= 1return currentdef reverseLinkedList(head, k):"""翻转链表的一部分。:param head: 部分链表的头节点:param k: 节点数量:return: 翻转后的链表头节点"""previous, current = None, headwhile k:next_node = current.nextcurrent.next = previousprevious = currentcurrent = next_nodek -= 1return previous# 找到第 k 个节点kth_node = getKthNode(head, k)if not kth_node:return headnext_group_head = kth_node.nextkth_node.next = None# 翻转当前 k 个节点new_head = reverseLinkedList(head, k)# 递归处理剩余链表，并连接head.next = reverseKGroup(next_group_head, k)return new_headdef listToListNode(arr):"""将 Python 列表转换为链表。:param arr: Python 列表:return: 链表的头节点"""dummy = ListNode()current = dummyfor val in arr:current.next = ListNode(val)current = current.nextreturn dummy.nextdef listNodeToList(head):"""将链表转换为 Python 列表。:param head: 链表的头节点:return: Python 列表"""result = []while head:result.append(head.val)head = head.nextreturn resultdef testReverseKGroup():"""测试 reverseKGroup 函数。"""test_cases = [([1, 2, 3, 4, 5], 2),([1, 2, 3, 4, 5], 3),([1, 2, 3, 4, 5], 1),([1], 1),([1, 2], 2)]for i, (input_list, k) in enumerate(test_cases):head = listToListNode(input_list)new_head = reverseKGroup(head, k)output_list = listNodeToList(new_head)print(output_list)# 运行测试代码
testReverseKGroup()

 [2, 1, 4, 3, 5]
[3, 2, 1, 4, 5]
[1, 2, 3, 4, 5]
[1]
[2, 1]