Rotate a Linked List by K places

Given a singly linked list, the task is to rotate the list to the right by k places, where k is a non-negative integer.

Input-Output Examples

Example 1:

  • Input:
    • List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    • k: 2
  • Output: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

Example 2:

  • Input:
    • List: 0 -> 1 -> 2 -> NULL
    • k: 4
  • Output: 2 -> 0 -> 1 -> NULL

Example 3:

  • Input:
    • List: 1 -> 2 -> NULL
    • k: 0
  • Output: 1 -> 2 -> NULL

Approach:

To rotate the linked list to the right by k places, we need to follow these steps:

  1. Find the Length of the List:
    • Traverse the list to find its length and to get the last node.
  2. Connect the Last Node to the Head:
    • Make the list circular by connecting the last node to the head.
  3. Calculate the Effective Rotations:
    • Since rotating a list of length n by k places is the same as rotating by k % n places, calculate k = k % n.
  4. Find the New Head and Break the Circle:
    • Traverse the list to find the new head, which is (n - k) nodes from the start, and break the circular list.

C++ Program to rotate a Linked List by k places

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to rotate the list to the right by k places
ListNode* rotateRight(ListNode* head, int k) {
    if (!head || k == 0) return head;

    // Find the length of the list and the last node
    ListNode* current = head;
    int length = 1;
    while (current->next) {
        current = current->next;
        length++;
    }

    // Make the list circular
    current->next = head;

    // Calculate the effective rotations
    k = k % length;
    int stepsToNewHead = length - k;

    // Find the new head and break the circle
    for (int i = 0; i < stepsToNewHead; i++) {
        current = current->next;
    }

    head = current->next;
    current->next = NULL;

    return head;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // Rotate the list by 2 places
    head = rotateRight(head, 2);
    cout << "After rotating by 2 places: ";
    printList(head);

    return 0;
}

Java Program to rotate a Linked List by k places

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to rotate the list to the right by k places
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        
        // Find the length of the list and the last node
        ListNode current = head;
        int length = 1;
        while (current.next != null) {
            current = current.next;
            length++;
        }

        // Make the list circular
        current.next = head;

        // Calculate the effective rotations
        k = k % length;
        int stepsToNewHead = length - k;

        // Find the new head and break the circle
        for (int i = 0; i < stepsToNewHead; i++) {
            current = current.next;
        }

        head = current.next;
        current.next = null;

        return head;
    }

    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // Rotate the list by 2 places
        head = rotateRight(head, 2);
        System.out.print("After rotating by 2 places: ");
        printList(head);
    }
}

Python Program to rotate a Linked List by k places

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to rotate the list to the right by k places
def rotate_right(head, k):
    if not head or k == 0:
        return head

    # Find the length of the list and the last node
    current = head
    length = 1
    while current.next:
        current = current.next
        length += 1

    # Make the list circular
    current.next = head

    # Calculate the effective rotations
    k = k % length
    steps_to_new_head = length - k

    # Find the new head and break the circle
    for _ in range(steps_to_new_head):
        current = current.next

    head = current.next
    current.next = None

    return head

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Rotate the list by 2 places
head = rotate_right(head, 2)
print("After rotating by 2 places:", end=" ")
print_list(head)

Rotating a linked list to the right by k places can be efficiently handled by finding the length of the list, making the list circular, calculating the effective rotations, and then breaking the circle to get the new head.

DSA

8125

437

Related Articles