Reverse a Linked List II Editorial

Practice Problem Link: Reverse a Linked List II

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

Problem Statement

Given a linked list and two numbers left and right, reverse the nodes from position 'left' to position 'right'. Assume: left <= right.

Approach

• Find the addresses of the nodes at the left and right position by traversing the given list.
• Reverse the list from left to right separately.
• After the reversal, reattach the list in the original list at the same position.

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* reverse(ListNode *head) {
	ListNode* prevNode = NULL, *currentNode = head;
	while (currentNode != NULL) {
		ListNode* nextNode = currentNode->next;
		currentNode->next = prevNode;
		prevNode = currentNode;
		currentNode = nextNode;
	}
	return prevNode;
}
ListNode* reverseLinkedListRange(ListNode* head, int left, int right) {
	ListNode* currentNode = head;
	ListNode* startNode;
	ListNode* lastNode;
	int i = 1;
	while (currentNode != NULL) {
		if (i > right) {
			break;
		}
		if (i < left) {
			startNode = currentNode;
		}
		if (i == right) {
			lastNode = currentNode;
		}
		currentNode = currentNode->next;
		i++;
	}
	lastNode->next = NULL;
	if (left == 1) {
		lastNode = head;
		head = reverse(head);
	} else {
		lastNode = startNode->next;
		startNode->next = reverse(startNode->next);
	}
	lastNode->next = currentNode;
	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 reverse(ListNode head) {
		ListNode prevNode = null, currentNode = head;
		while (currentNode != null) {
			ListNode nextNode = currentNode.next;
			currentNode.next = prevNode;
			prevNode = currentNode;
			currentNode = nextNode;
		}
		return prevNode;
	}
	ListNode reverseLinkedListRange(ListNode head, int left, int right) {
		ListNode currentNode = head;
		ListNode startNode = null;
		ListNode lastNode = null;
		int i = 1;
		while (currentNode != null) {
			if (i > right) {
				break;
			}
			if (i < left) {
				startNode = currentNode;
			}
			if (i == right) {
				lastNode = currentNode;
			}
			currentNode = currentNode.next;
			i++;
		}
		lastNode.next = null;
		if (left == 1) {
			lastNode = head;
			head = reverse(head);
		} else {
			lastNode = startNode.next;
			startNode.next = reverse(startNode.next);
		}
		lastNode.next = currentNode;
		return head;
	}
}