Rotate a Linked List Editorial

Practice Problem Link: Rotate A Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list, rotate it to the right by k nodes.

Approach

Traverse the given linked list. Since the rotation is to the right, therefore (n - k)th node will be the new last node and it will point to NULL. The node just after this node will be the new head and the last node during the traversal will now point to the previous head node.

Note: If k is greater than n then change k to k%n.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* rotateListByK(ListNode* head, int k) {
	if (head == NULL || head->next == NULL) {
		return head;
	}
	int totalLength = 0;
	ListNode* currentNode = head;
	while (currentNode != NULL) {
		totalLength++;
		currentNode = currentNode->next;
	}
	k = k % totalLength;
	if (k == 0) {
		return head;
	}
	k = totalLength - k;
	currentNode = head;
	int cnt = 1;
	ListNode *temp;
    while (currentNode->next != NULL) {
		if(cnt == k) {
			temp = currentNode->next;
			currentNode->next = NULL;
			currentNode = temp;
		} else {
			currentNode = currentNode->next;
		}
		cnt++;
	}
	currentNode->next = head;
    head = temp;
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode rotateListByK(ListNode head, int k) {
		if (head == null || head.next == null) {
			return head;
		}
		int totalLength = 0;
		ListNode currentNode = head;
		while (currentNode != null) {
			totalLength++;
			currentNode = currentNode.next;
		}
		k = k % totalLength;
		if (k == 0) {
			return head;
		}
		k = totalLength - k;
		currentNode = head;
		int cnt = 1;
		ListNode temp = null;
		while (currentNode.next != null) {
			if(cnt == k) {
				temp = currentNode.next;
				currentNode.next = null;
				currentNode = temp;
			} else {
				currentNode = currentNode.next;
			}
			cnt++;
		}
		currentNode.next = head;
		head = temp;
		return head;
	}
}