[LeetCode] Rotate List

Problem: 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]

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

Approach: This is an implementation problem. Just look at the implementation to understand it. Basically to rotate list right, we need to get the kth node from the end. Say its called kthNode. We also need to get end node as it's next will be current head and (k-1)th next will be null.

The kthNode will be the new head. That's all!

Implementation in C#:

    public ListNode RotateRight(ListNode head, int k)

    {

        if (head?.next == null || k == 0)

        {

            return head;

        }

        int length = this.GetLength(head);

        if (length <= k)

        {

            if (k % length == 0)

            {

                return head;

            }

            k = k % length;

        }

        ListNode curr = head;

        ListNode fwd = head;

        for (int i = 0; i < k; ++i)

        {

            fwd = fwd.next;

        }

        while (fwd.next != null)

        {

            curr = curr.next;

            fwd = fwd.next;

        }

        fwd.next = head;

        head = curr.next;

        curr.next = null;

        return head;

    }

    private int GetLength(ListNode node)

    {

        int count = 0;

        while (node != null)

        {

            node = node.next;

            ++count;

        }

        return count;

    }

Complexity: O(n)