Merge Two Sorted Linked List Editorial

Practice Problem Link: Merge Two Sorted Linked List

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

Problem Statement

Given two sorted linked lists, merge them inplace to produce a singular sorted linked list.

Approach

Make the smaller head of the two lists as the head of the merged list. Now traverse both the list simultaneously. Append the node having a smaller value at the end of the merged list and move the pointer to the next node in that particular 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* mergeTwoSortedList (ListNode* firstList, ListNode* secondList) {
	ListNode *temp;
    if(firstList->data > secondList->data) {
            temp = firstList;
            firstList = secondList;
            secondList = temp;
    }
	ListNode *head = firstList; 
	ListNode *prev = firstList; 
	firstList = firstList->next;
	while (firstList != NULL && secondList != NULL){
		if(firstList->data > secondList->data) {
			prev->next = secondList; 
			temp = firstList;
			firstList = secondList;
			secondList = temp;
		}
		prev = firstList; 
		firstList = firstList->next;
	}
	prev->next = secondList;
	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 mergeTwoSortedList (ListNode firstList, ListNode secondList) {
	    ListNode temp;
		if(firstList.data > secondList.data) {
				temp = firstList;
				firstList = secondList;
				secondList = temp;
		}
		ListNode head = firstList; 
		ListNode prev = firstList; 
		firstList = firstList.next;
		while (firstList != null && secondList != null){
			if(firstList.data > secondList.data) {
				prev.next = secondList; 
				temp = firstList;
				firstList = secondList;
				secondList = temp;
			}
			prev = firstList; 
			firstList = firstList.next;
		}
		prev.next = secondList;
		return head;
	}
}