25.Reverse Nodes in k-Group

Tags: [list], [linked_list], [reverse], [reverse_linked_list]

Com: {fb}

Link: https://leetcode.com/problems/reverse-nodes-in-k-group/\#/description

Given a linked list, reverse the nodes of a linked listkat a time and return its modified list.

kis a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple ofkthen 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

Fork= 2, you should return:2->1->4->3->5

Fork= 3, you should return:3->2->1->4->5

Solution:

# 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
        """
        if not head or not k:
            return head

        prev = None
        curr = head
        counter = 1
        while curr:
            if counter == k:
                if not prev:
                    next = curr.next
                    curr.next = None
                    new_head = self.reverse_list(head)
                    head.next = next
                    prev = head
                    head = new_head
                    curr = next
                else:
                    next = curr.next
                    curr.next = None
                    old_head = prev.next
                    prev.next = None
                    new_head = self.reverse_list(old_head)
                    old_head.next = next
                    prev.next = new_head
                    prev = old_head
                    curr = next

                counter = 1
                continue

            counter += 1
            curr = curr.next

        return head

    def reverse_list(self, head):
        if not head or not head.next:
            return head

        prev = None
        curr = head
        next = None
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

Revelation:

• Initialize the counter to 1, so when counter == k, the curr is pointing to the end of the target sub list.
• Before reversing the sub list, we need cut off the sub list from the main list, prev.next = None, curr.next = None.

Note:

• Time complexity = O(n), n is the number of nodes of the given list.
• Space complexity = O(1).