Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 

Output: 1->1->2->3->4->4 

Solution:

The approach here is similar to the "merge" step in Merge Sort.

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* public int val;
	* public ListNode next;
	* public ListNode(int val=0, ListNode next=null) {
	* this.val = val;
	* this.next = next;
	* }
	* }
	*/
	public class Solution {
	public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
	ListNode newList = new ListNode();
	ListNode dummyHead = newList;
	ListNode l1temp = l1;
	ListNode l2temp = l2;
	while(l1temp!=null && l2temp!=null){
	if(l1temp.val<l2temp.val){
	dummyHead.next = new ListNode(l1temp.val);
	l1temp = l1temp.next;
	}
	else{
	dummyHead.next = new ListNode(l2temp.val);
	l2temp = l2temp.next;
	}
	dummyHead = dummyHead.next;
	}
	if(l1temp == null){
	while(l2temp!=null){
	dummyHead.next = new ListNode(l2temp.val);
	l2temp = l2temp.next;
	dummyHead = dummyHead.next;
	}
	}
	if(l2temp == null){
	while(l1temp!=null){
	dummyHead.next = new ListNode(l1temp.val);
	l1temp = l1temp.next;
	dummyHead = dummyHead.next;
	}
	}
	return newList.next;
	}
	}

view raw MergeTwoLists.cs hosted with ❤ by GitHub

Time Complexity: O(m+n) where m and n are length of two linked lists.

Space Complexity: O(m+n) where m and n are length of two linked lists.