Reverse Nodes in k-Group
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.
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
take a look 511 Swap Two Nodes in Linked List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @param k, an integer
# @return a ListNode
def getLen(self, head):
len = 0
node = head
while node:
len += 1
node = node.next
return len
def reverseNextK(self, head, k):
n = self.getLen(head.next)
if n < k:
return None
prev = head
p1, curr = head.next, head.next
for i in range(k):
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
p1.next = curr
head.next = prev
return p1
def reverseKGroup(self, head, k):
if head == None or head.next == None or self.getLen(head) < k:
return head
dummy = ListNode(0)
dummy.next = head
head = dummy
while head and head.next:
head = self.reverseNextK(head, k)
return dummy.next
Last updated
Was this helpful?