Merge Sort Linked List Editorial

Practice Problem Link: Merge Sort Linked List

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

Problem Statement

Given a linked list, sort it using merge sort.

Approach

Merge sort is a divide and conquer algorithm. 

• Traverse the given list and find its middle node.
• Divide the list into two parts about the middle node.
• Sort both the parts recursively and then merge them to get the final sorted list.

Note: A list having only one element is considered to be sorted.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(log(n))

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* getMid(ListNode* head) {
	ListNode* slowPtr = head;
	ListNode* fastPtr = head->next->next;
	while (fastPtr != NULL && fastPtr->next != NULL) {
		slowPtr = slowPtr->next;
		fastPtr = fastPtr->next->next;
	}
	return slowPtr;
}
ListNode* merge(ListNode* firstHalf, ListNode* secondHalf) {
	ListNode* mergedList;
	if (firstHalf->data < secondHalf->data) {
		mergedList = firstHalf;
		firstHalf = firstHalf->next;
	} else {
		mergedList = secondHalf;
		secondHalf = secondHalf->next;
	}
	ListNode* currentNode = mergedList;
	while (firstHalf != NULL && secondHalf != NULL) {
		if (firstHalf->data < secondHalf->data) {
			currentNode->next = firstHalf;
			firstHalf = firstHalf->next;
		} else {
			currentNode->next = secondHalf;
			secondHalf = secondHalf->next;
		}
		currentNode = currentNode->next;
	}
	while (firstHalf != NULL) {
		currentNode->next = firstHalf;
		firstHalf = firstHalf->next;
		currentNode = currentNode->next;
	}
	while (secondHalf != NULL) {
		currentNode->next = secondHalf;
		secondHalf = secondHalf->next;
		currentNode = currentNode->next;
	}
	return mergedList;
}
ListNode* mergeSort(ListNode* head) {
	if (head->next == NULL) {
		return head;
	}
	ListNode* midNode = getMid (head);
	ListNode* secondHalf = mergeSort(midNode->next);
	midNode->next = NULL;
	ListNode* firstHalf = mergeSort(head);
	return merge(firstHalf, secondHalf);
}

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 getMid(ListNode head) {
		ListNode slowPtr = head;
		ListNode fastPtr = head.next.next;
		while (fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}
		return slowPtr;
	}
	ListNode merge(ListNode firstHalf, ListNode secondHalf) {
		ListNode mergedList;
		if (firstHalf.data < secondHalf.data) {
			mergedList = firstHalf;
			firstHalf = firstHalf.next;
		} else {
			mergedList = secondHalf;
			secondHalf = secondHalf.next;
		}
		ListNode currentNode = mergedList;
		while (firstHalf != null && secondHalf != null) {
			if (firstHalf.data < secondHalf.data) {
				currentNode.next = firstHalf;
				firstHalf = firstHalf.next;
			} else {
				currentNode.next = secondHalf;
				secondHalf = secondHalf.next;
			}
			currentNode = currentNode.next;
		}
		while (firstHalf != null) {
			currentNode.next = firstHalf;
			firstHalf = firstHalf.next;
			currentNode = currentNode.next;
		}
		while (secondHalf != null) {
			currentNode.next = secondHalf;
			secondHalf = secondHalf.next;
			currentNode = currentNode.next;
		}
		return mergedList;
	}
	ListNode mergeSort(ListNode head) {
		if (head.next == null) {
			return head;
		}
		ListNode midNode = getMid (head);
		ListNode secondHalf = mergeSort(midNode.next);
		midNode.next = null;
		ListNode firstHalf = mergeSort(head);
		return merge(firstHalf, secondHalf);
	}
}