Problem Statement#

We have to implement the mergeTwoLists function that takes the head nodes of two sorted linked lists as input and returns the head node of the merged linked list as the output.

Optimal Solution#

To merge both linked lists we can use the two-pointer approach by maintaining an iterator on both linked lists and comparing their values. The smaller value will be selected and inserted at the end of a new list. The result would be a merged sorted linked list.

If all the values from any one of the linked lists are added then the other linked list will be joined at the end of the merged linked list.

Psuedo-code for the Optimal Solution#

if(linked_list2==nil){
}

while(temp1!=nil and temp2!=nil){
if (temp1.value < temp2.value){
temp1=temp1.next
} else {
temp2=temp2.next
}
}

if(temp1!=nil){
} else if(temp2!=nil){
}



Time Complexity Analysis#

Best Case Scenario#

For the best case input i.e. either the first or second linked list is empty, the time complexity of the solution is $O(1)$ because we are returning the non-empty linked list as the result.

Worst Case Scenario#

In the worst-case scenario, we have to iterate over both the linked lists completely. But since we are iterating them together using two pointers the time complexity will be determined by the length of the larger linked list.

So the total time complexity of the solution in the worst-case scenario will be $O(n)$ where $n$ is the size of the larger linked list.

Space Complexity Analysis#

The merged linked list will contain all the elements from both input lists (with repetition). If the length of both linked lists is $m$ and $n$, the additional memory space required by the solution will be $O(m+n)$.

Code for the Optimal Solution#

package main

import "fmt"

type ListNode struct {
Val int
Next *ListNode
}

func Display(ln *ListNode){
temp := ln
for(temp!=nil){
fmt.Printf("%d->", temp.Val)
temp=temp.Next
}
fmt.Println()
}

func InsertAtEnd(list *ListNode, value int)(*ListNode){
if list==nil{
list = &(ListNode{Val:value})
} else {
temp := list
for(temp.Next!=nil){
temp=temp.Next
}
temp.Next = &(ListNode{Val:value})
}
return list
}

func JoinLists(list1 *ListNode, list2 *ListNode)(*ListNode){
// Joins list1 with list2 by the last node
temp := list1
for(temp.Next!=nil){
temp=temp.Next
}
temp.Next = list2
return list1
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode)(*ListNode){
// Checking if any of the input lists are empty
if(list1==nil){
return list2
} else if(list2==nil) {
return list1
}

temp1 := list1
temp2 := list2
var mergedList *ListNode

// Loop over both linked lists until one of them/both
// are empty
for((temp1!=nil)&&(temp2!=nil)){

// If the current value in the first list is smaller
// then add it to the merged linked list and vice versa
if(temp1.Val<temp2.Val){
mergedList = InsertAtEnd(mergedList, temp1.Val)
temp1=temp1.Next
} else {
mergedList = InsertAtEnd(mergedList, temp2.Val)
temp2=temp2.Next
}
}

// If any one of the linked list is not empty
if(temp1!=nil){
mergedList = JoinLists(mergedList, temp1)
} else if(temp2!=nil){
mergedList = JoinLists(mergedList, temp2)
}
return mergedList
}

func main(){
var ln *ListNode
ln = InsertAtEnd(ln, 5)
ln = InsertAtEnd(ln, 7)
ln = InsertAtEnd(ln, 20)
ln = InsertAtEnd(ln, 34)
ln = InsertAtEnd(ln, 42)
Display(ln)

var ln2 *ListNode
ln2 = InsertAtEnd(ln2, 2)
ln2 = InsertAtEnd(ln2, 4)
ln2 = InsertAtEnd(ln2, 6)
ln2 = InsertAtEnd(ln2, 14)
ln2 = InsertAtEnd(ln2, 66)
Display(ln2)

Display(mergeTwoLists(ln, ln2))
}

// Output