题目-困难难度

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

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

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

示例

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：

你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 链表转列表 -> 计算 -> 列表转链表

时间
60ms
击败 26.88%使用 Python3 的用户
内存
17.36mb
击败 5.01%使用 Python3 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:li = []while head:li.append(head.val)head = head.nextfor i in range(0,len(li),k):if i > len(li)-k:breakli[i:i+k] = li[i:i+k][::-1]nh = ListNode(li[0])p = nhfor i in range(1,len(li)):p.next = ListNode(li[i])p = p.nextreturn nh

2. 反转+合并

时间
44ms
击败 12.61%使用 Python 的用户
内存
15.42mb
击败 5.04%使用 Python 的用户

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def reverseKGroup(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""def reverse_ll(head):prev = Nonecur = headwhile cur:nn = cur.nextcur.next = prevprev = curcur = nnreturn prevdef combine_ll(l1,l2):if not l1:return l2if not l2:return l1cur = l1while cur.next:cur = cur.nextcur.next = l2return l1# 结果链表res = ListNode()# 遍历headc = headwhile c:i = 0nh = ListNode()p = nh# 按k数量集群遍历while i < k and c:p.next = ListNode(c.val)i+=1p = p.nextc = c.next # 达到k数量，进行反转合并if i == k:nl = reverse_ll(nh.next)res =combine_ll(res,nl)# 未达到，则仅进行合并else:res =combine_ll(res,nh.next)return res.next