Solving the LeetCode "Rotate List" Problem in Go

Difficulty: Medium | Tags: Linked List, Two Pointers

Introduction

Rotating a linked list involves shifting the list's nodes to the right by a given number of positions. This problem tests understanding of linked list manipulation and efficient traversal techniques.

Problem Analysis

The task is to rotate a linked list to the right by k places. For example, rotating [1,2,3,4,5] by 2 results in [4,5,1,2,3]. If k is larger than the list length, we take k modulo the length to avoid unnecessary rotations.

Solution Approach

First, find the length of the list. Then, compute the effective rotation count using modulo. Connect the tail to the head to form a circular list. Traverse to the new tail (length - k steps from the original tail) and break the circular connection to form the rotated list.

Go Implementation

/**
* 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
        }
        // Compute the length of the list
        length := 1
        tail := head
        for tail.Next != nil {
            tail = tail.Next
            length++
        }
        // Adjust k to avoid unnecessary rotations
        k = k % length
        if k == 0 {
            return head
        }
        // Make the list circular
        tail.Next = head
        // Find the new tail (length - k steps from head)
        newTail := head
        for i := 0; i < length-k-1; i++ {
            newTail = newTail.Next
        }
        // The new head is the node after newTail
        newHead := newTail.Next
        newTail.Next = nil
        return newHead
    }

Complexity Analysis

Time complexity: O(n), where n is the number of nodes. We traverse the list twice: once to find the length and once to find the new tail. Space complexity: O(1), as we use a constant amount of extra space.

Testing and Examples

Test cases include rotating a list by k=2 ([1,2,3,4,5] → [4,5,1,2,3]), k=4 ([0,1,2] → [2,0,1]), and edge cases like empty list or k=0.

Best Practices and Tips

Always handle edge cases (empty list, single node, k=0). Use modulo to reduce k efficiently. Visualizing the circular list helps in understanding the rotation logic.