How to Reverse a Linked List in groups of given size

[Question]: Given the head of a linked list, reverse the nodes of the list k at a time, and return the updated list. k is 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 of k then left-out nodes, in the end, should remain as it is.

Criteria: Don’t alter the values in the list’s nodes, only nodes themselves may be changed.
Example:-
Input: 1->2->3->4->5->6->7->8->NULL, K = 3 
Output: 3->2->1->6->5->4->8->7->NULL 

Approach# Recursive solution. curr node points to k+1 now reverse the nodes with the subset.

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    var curr = head
    var headyCopy = head
    var count = 0
    while curr != nil && count != k {// Find K+1 Node
        curr = curr?.next
        count+=1
    }
    if count == k {// if k+1 node is found
        curr = reverseKGroup(curr,k)// reverse list with k+1 node as head
        // headCopy - head-pointer to direct part,
        // curr - head-pointer to reversed part
        while count > 0 {// reverse current k-group:
            var tmp = headyCopy?.next // tmp - next head in direct part
            headyCopy?.next = curr// preappending "direct" headCopy to the reversed list
            curr = headyCopy // move head of reversed part to a new node
            headyCopy = tmp // move "direct" headCopy to the next node in direct part
            count-=1
        }
        headyCopy = curr
    }
    return headyCopy
}

let kGroupLinkedListInput = ListNode(1, ListNode(2, ListNode(3,ListNode(4, ListNode(5)))))
let kGroupLinkedListOutput = reverseKGroup(kGroupLinkedListInput, 2)
print("Output of kth nummber reversed linked list is ---", kGroupLinkedListOutput!)// 2 1 4 3 5

Leave a Comment

Your email address will not be published. Required fields are marked *