给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverse(self, head, k):
p = head
for i in range(k): # 先检验够不够数
p = p.next
if p is None:
return None
p = head.next.next
last = head.next
for i in range(k - 1): # 翻转
last.next = p.next
p.next = head.next
head.next = p
p = last.next
return last
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k < 2:
return head
dummy = ListNode(0)
dummy.next = head
p = dummy
while p is not None:
p = self.reverse(p, k)
return last.next
翻转
翻转的思想是,把p一个挨一个的拎到head后面
比如1 2 3 4 5,k = 3 加上dummy为 0 1 2 3 4 5
第1趟循环: 0 1 2 3 4 5
head --> 0, last --> 1,p --> 2
把2拎到0的后面,变成0 2 1 3 4 5
第2趟循环:0 2 1 3 4 5
head --> 0, last --> 1,p --> 3
把3拎到0的后面,变成0 3 2 1 4 5
第3趟循环:0 3 2 1 4 5
head --> 0, last --> 1,p --> 4
把4拎到0的后面,变成0 4 3 2 1 5
循环了k-1次即3次,循环退出
最后得 4 3 2 1 5
网友评论