[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