Rotate List

1. Problem Description

Given the head head of a linked list, rotate the list to the right by k positions.

2. Approach

3. Implementation

3.1. Fast and Slow Pointers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil ||  k == 0 {return head}

    length := getLength(head)
    if k > length { k = k % length }
    if k == 0 {return head}

    dummyHead := &ListNode{Next:head}
    fast := dummyHead
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    slow := dummyHead
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    newHead := slow.Next
    slow.Next = nil
    fast.Next = dummyHead.Next
    return newHead
}


func getLength(head *ListNode) int {
    count := 0
    for head != nil {
        count++
        head = head.Next
    }
    return count
}

4. References

• 61. Rotate List - LeetCode