Posts Rotate a Linked List (geeksforgeeks - SDE Sheet)
Post
Cancel

Rotate a Linked List (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given the head of a singly linked list, the task is to rotate the left shift of the linked list by k nodes, where k is a given positive integer smaller than or equal to the length of the linked list.

geeksforgeeks

SOLUTION

We can solve this by first reversing the entire linked list, then splitting it into two parts based on the given rotation value k, and reversing both parts individually. After reversing the two halves, we reconnect them to form the final rotated list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {

    public Node rotate(Node head, int k) {

        // Get the length of the linked list
        int n = lengthLinkedList(head);

        // Reverse the entire linked list
        head = reverseLinkedList(head);

        // The linked list will be split into two parts. We will reverse both parts separately.
        Node h1 = head; // First half will start from the head
        Node h2 = head; // Second half will be determined later

        // If k is more than the length of the list, reduce k using modulo operation
        k = k % n;

        // Move h2 pointer n-k-1 steps forward to find the end of the first part
        for(int i = 0; i < n - k - 1; i++){
            h2 = h2.next;
        }

        // Save the tail of the first part of the list (end of first half)
        Node t1 = h2;

        // h2 now points to the head of the second part of the list
        h2 = h2.next;

        // Break the list into two parts by setting the next of t1 to null
        t1.next = null;

        // We'll use this temp variable to link the two parts together later
        Node temp = h1;

        // Reverse the first half of the list
        h1 = reverseLinkedList(h1);

        // Reverse the second half of the list
        h2 = reverseLinkedList(h2);

        // Join the two parts: the tail of the first part will point to the head of the second part
        temp.next = h2;

        // Return the new head of the rotated linked list
        return h1;
    }

    // Helper function to find the length of the linked list
    int lengthLinkedList(Node head){
        int count = 0;
        while(head != null){
            count++;
            head = head.next;
        }
        return count;
    }

    // Helper function to reverse a linked list
    Node reverseLinkedList(Node head){
        Node h1 = head;
        Node h2 = null;

        while(h1 != null){
            Node t = h1;
            h1 = h1.next;
            t.next = h2;
            h2 = t;
        }
        return h2;
    }
}

This post is licensed under CC BY 4.0 by the author.