How to rotate linked list with K-th places ?

[Question]: Given the head of a linked list, rotate the list to the right by k places.
Example: –

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

#Approach
Step: 1 Create tail node which moves till ends
Step: 2 Create curr the tail node is the (len-k)-th node (1st node is head)
Step: 3 Reorder linked list

func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
    // Base case
    guard head?.next != nil, k > 0 else { return head }
    
    // Find length and tail
    var tail = head, length = 1
    while tail?.next != nil {
        tail = tail?.next
        length += 1
    }
    
    // Reduce k
    var k = k % length// because if 5%5 encounters it gives 0(Not to rotate.)
    if k == 0 { return head }
    
    // Find the pivot
    var curr = head
    for _ in 0..<length - k - 1 {
        curr = curr?.next// the tail node is the (len-k)-th node (1st node is head)
    }
    // Reorder the list
    let newHead = curr?.next
    curr?.next = nil
    tail?.next = head
    //        print("head ----->", head)
    //        print("curr ----->", curr)
    //        print("tail ----->", tail)
    //        print("newHead -->", newHead)
    
    return newHead
}

let rotateLinkListInput = ListNode(1, ListNode(2, ListNode(3,ListNode(4, ListNode(5)))))
let rotateLinkListOutput = rotateRight(rotateLinkListInput, 2)
//print("Output of rotateLinkListOutput is ---", rotateLinkListOutput!)// 4 5 1 2 3

Leave a Comment

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