Leetcode 25: Reverse Nodes in k-Group

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;
}