https://leetcode.com/problems/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.
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
Code
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def rotate(self, pt1, k):
'''
# return:
# pt1: the new head of the current k elements
# pt2: the head of the next k elements
# i: the number of elements just being rotated
'''
i = 2
pt2 = pt1.next
pt1.next = None
while i<=k and pt2:
pt3 = pt2.next
pt2.next = pt1
pt1 = pt2
pt2 = pt3
i += 1
return pt1, pt2, i
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k == 1 or head is None or head.next is None:
return head
new_head = None
tail = ListNode(999) # tail is the last k elements's last element.
# Dummy at the beginning.
pt1 = head
while pt1:
# pt1 will become the new head in the current k elements
# pt2 will become the head of the next k elements
pt1, pt2, i = self.rotate(pt1, k)
# rotation reaches the end but the elements in the rotation are less than k
if pt2 is None and i<=k:
pt1, pt2, _ = self.rotate(pt1, k)
if not new_head:
new_head = pt1
tail.next = pt1
tail = head
head = pt2
# Set pt1 to be the new head in the next k elements
pt1 = pt2
return new_head
Idea
What I implemented is pretty straightforward in iterative way: find the first k elements and rotate them, then start to rotate the next k elements, so on so forth. When we reach the last k’ elements (k’ <= k), we need to check if we need to rotate them or not.
More trick way is to implement the solution in a recursive way (ref: https://leetcode.com/discuss/21301/short-but-recursive-java-code-with-comments):
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
head = curr;
}
return head;
}