Reorder List Editorial

Practice Problem Link: Reorder List

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

Problem Statement

Given a linked list of the form:

N0 -> N1 -> N2 -> ....Nn-2 -> Nn-1

Reorder the list in the following format:

N0 -> Nn-1 -> N1 -> Nn-2 -> N2 -> ....

Naive Approach

Traverse the given linked list and for each node:

• Go to the last node of the list remove it from there and insert it after the current node.
• Move the current node two steps ahead.

Analysis

• Time Complexity: O(n2)
• 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* reorderList(ListNode* head) {
	ListNode* currentNode = head;
	while (currentNode != NULL) {
		ListNode* last = currentNode;
		while (last != NULL && last->next != NULL && last->next->next != NULL) {
			last = last->next;
		}
		if (currentNode == last) {
			break;
		}
		last->next->next = currentNode->next;
		currentNode->next = last->next;
		currentNode = currentNode->next->next;
		last->next = NULL;
	}
	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 reorderList(ListNode head) {
		ListNode currentNode = head;
		while (currentNode != null) {
			ListNode last = currentNode;
			while (last != null && last.next != null && last.next.next != null) {
				last = last.next;
			}
			if (currentNode == last) {
				break;
			}
			last.next.next = currentNode.next;
			currentNode.next = last.next;
			currentNode = currentNode.next.next;
			last.next = null;
		}
		return head;
	}
}

Optimal Approach

• Divide the given list into two parts about the middle node.
• Reverse the second half of the list and then merge both the lists alternatively.
• Return the head of the resultant list.

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, *currNode = head, *nextNode;
	while (currNode != NULL) {
		nextNode = currNode->next;
		currNode->next = prevNode;
		prevNode = currNode;
		currNode = nextNode;
	}
	return prevNode;
}
ListNode* reorderList(ListNode* head) {
	if (head == NULL) {
		return head;
	}
	ListNode* slowPtr = head, *fastPtr = head->next;
	while (fastPtr != NULL && fastPtr->next != NULL) {
		slowPtr = slowPtr->next;
		fastPtr = fastPtr->next->next;
	}
	ListNode* firstHalf = head, *secondHalf = slowPtr->next;
	slowPtr->next = NULL;
	secondHalf = reverse(secondHalf);
	while (firstHalf != NULL && secondHalf != NULL) {
		ListNode* temp = secondHalf->next;
		secondHalf->next = firstHalf->next;
		firstHalf->next = secondHalf;
		secondHalf = temp;
		firstHalf = firstHalf->next->next;
	}
	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, currNode = head, nextNode;
		while (currNode != null) {
			nextNode = currNode.next;
			currNode.next = prevNode;
			prevNode = currNode;
			currNode = nextNode;
		}
		return prevNode;
	}
	ListNode reorderList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode slowPtr = head, fastPtr = head.next;
		while (fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}
		ListNode firstHalf = head, secondHalf = slowPtr.next;
		slowPtr.next = null;
		secondHalf = reverse(secondHalf);
		while (firstHalf != null && secondHalf != null) {
			ListNode temp = secondHalf.next;
			secondHalf.next = firstHalf.next;
			firstHalf.next = secondHalf;
			secondHalf = temp;
			firstHalf = firstHalf.next.next;
		}
		return head;
	}
}