Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Solution
(Reverse-Nodes-in-k-Group.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
def reverse(l):
newEnd = l
tmp = l.next
while tmp != None:
n = tmp.next
tmp.next = l
l = tmp
tmp = n
newEnd.next = None
# 需要返回newEnd,就是下一个节点的prev
return [l,newEnd]
def findEnd(start,k):
i = 1
ret = start
while i < k and ret != None:
i += 1
ret = ret.next
return ret
newNode = ListNode(-1)
newNode.next = head
prev = newNode
start = head
while start!= None and start.next != None:
end = findEnd(start,k)
if end == None:
return newNode.next
nextNode = end.next
end.next = None
ret= reverse(start)
# 把 reversed substring 和现有的连起来
prev.next = ret[0]
ret[1].next = nextNode
start = nextNode
prev = ret[1]
return newNode.next
|