Rotate A Linked List

Problem Statement

You are given the head of a singly linked list and an integer K, write a program to Rotate the Linked List in a clockwise direction by K positions from the last node.

Example

Input-1

Output-1

Explanation

Here, we have rotated the linked list exactly 2 times. On the First rotation 5 becomes head and 4 becomes tail, and on the second rotation 4 becomes head and 3 becomes the tail node.

Input-2

Output-2

Explanation

Here, we have rotated the linked list exactly 4 times. As you can see below.

Constraints

Algorithm 1 - Just by Changing the Next Pointer for Any kth Node

Intuition:

In this approach, we need to maintain three-pointers to (k+1)^th^ node, kth node, and the previous node. The idea here is to traverse through the linked list until the kth node, then change the k+1^th^ node to NULL and the next pointer of the last node should point to the current head node after that make the k+1^th^ node a new head of the linked list.

Algorithm

1. Check whether the head is null or k == 0. If so, return.
2. Initialize a variable that will store the number of nodes in the linked list and set the variable count to 1 (for head).
3. Traverse through the linked list until the kth node.
4. If the current is NULL or k^th^ node is greater than or equal to the number of nodes in a linked list. Don't change the list in this case, Hence return.
5. Now traverse through all the nodes linked list till the end and change next pointer of the last node to previous head.
6. Finally the change head to k+1^th^ node and then change the k+1^th^ node to NULL.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n). Since we traversed the linked list only once to rotate a linked list, where n is the size of the linked list.

Space Complexity

The space complexity is O(1). Since no extra space is used in the Program to rotate a linked list.

Algorithm 2 - By Rotating K Nodes

Intuition:

The idea here is is similar to the previous one the only difference is to first convert the singly linked list to a circular linked list and then move k-1 steps forward from the head node but before moving, make the k-1^th^ node next to null and next node as head.

Algorithm

1. Check whether the head is null or k == 0. If so, return.
2. Initialize a variable length that will store the number of nodes in the linked list and set the variable count to 1 (for head).
3. Link the last node to the head by pointing next to the last node to the head as it will convert the singly linked list to a circular list.
4. Traverse the linked list to k-1^th position which will be last element.
5. Iterate over the last node and break the linked list by pointing the last node to null.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n). Since we traversed the linked list only once to rotate a linked list, where n is the size of the linked list.

Space Complexity

The space complexity is O(1). Since no extra space is used in the Program to rotate a linked list.