Leetcode-每日一题【25.k个一组翻转链表】

**每日一题:25. k 个一组翻转链表**

### 题目描述给定一个链表, 每 k 个节点一组, 将它们反转并返回新的链表。

### 示例输入: `1->2->3->4->5`, k =2输出: `2->1->4->3->5`

### 解决方案#### 方法1: 递归法

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef reverseKGroup(head, k):
 """
 :type head: ListNode :type k: int :rtype: ListNode """
 # 递归函数, 每次反转一个组 def reverse(start, end):
 prev = None cur = start while cur != end:
 next_node = cur.next cur.next = prev prev = cur cur = next_node return prev # 初始化指针 dummy = ListNode(0)
 dummy.next = head pre = dummy # 开始反转链表 while True:
 # 计算当前组的起始和结束位置 start = pre.next end = getEnd(start, k)
 # 如果剩余节点不足 k 个, 直接返回原链表 if not end:
 break # 反转当前组 new_head = reverse(start, end +1)
 # 将反转后的新头连接到前一个组的尾部 pre.next = new_head pre = start return dummy.nextdef getEnd(start, k):
 """
 :type start: ListNode :type k: int :rtype: ListNode """
 # 计算当前组的结束位置 end = start for _ in range(1, k):
 if not end:
 return None end = end.next return end# 测试代码def printList(head):
 while head:
 print(head.val, end=" ")
 head = head.next print()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k =2new_head = reverseKGroup(head, k)
printList(new_head) # 输出:21435

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef reverseKGroup(head, k):
 """
 :type head: ListNode :type k: int :rtype: ListNode """
 # 初始化指针 dummy = ListNode(0)
 dummy.next = head pre = dummy while True:
 # 计算当前组的起始和结束位置 start = pre.next end = getEnd(start, k)
 # 如果剩余节点不足 k 个, 直接返回原链表 if not end:
 break # 反转当前组 new_head = reverse(start, end +1)
 # 将反转后的新头连接到前一个组的尾部 pre.next = new_head pre = start return dummy.nextdef getEnd(start, k):
 """
 :type start: ListNode :type k: int :rtype: ListNode """
 # 计算当前组的结束位置 end = start for _ in range(1, k):
 if not end:
 return None end = end.next return enddef reverse(start, end):
 """
 :type start: ListNode :type end: ListNode :rtype: ListNode """
 # 反转链表 prev = None cur = start while cur != end:
 next_node = cur.next cur.next = prev prev = cur cur = next_node return prev# 测试代码def printList(head):
 while head:
 print(head.val, end=" ")
 head = head.next print()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k =2new_head = reverseKGroup(head, k)
printList(new_head) # 输出:21435