Skip to main content

Reverse Nodes in k-Group

Question​

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

What is the most efficient algorithm to reverse a linked list in groups of k nodes?

Example 1
Input: 1->2->3->4->5->NULL, k = 2
Output: 2->1->4->3->5->NULL

Solution​

all//Reverse Nodes in k-Group.py


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseKGroup(self, head, k):
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        while head:
            tail = pre
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        return dummy.next

    def reverse(self, head, tail):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head