PROBLEM DESCRIPTION
Merge two LinkedList which are sorted such that the final LinkedList is also sorted. (Without creating a new LinkedList)
SOLUTION
This problem is also part of AlgoExpert: https://www.algoexpert.io/questions/merge-linked-lists
The idea is to first decide which linkedlist we are going to modify to represent the final linked list. Then we keep adding elements from the other list to this list. The way we do it is, we keep moving foward on the first list. If the node in the 2nd list has a value less than the current node, then we add that node before the current node in list1. If it’s greater, then we keep moving forward. Since we need to add the element from list2 behind the current node of list1, we also track the previous node in list1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
class Program {
public static LinkedList mergeLinkedLists(LinkedList headOne, LinkedList headTwo) {
LinkedList p = null, t1 = headOne, t2 = headTwo;
while(t1 != null && t2 != null){
if(t2.value <= t1.value){
//t2 should come before t1
if(p==null){
//edge-case when p is null (first update)
p = t2;
t2 = t2.next;
p.next = t1;
}else{
p.next = t2;
p = t2;
t2 = t2.next;
p.next = t1;
}
}else{
p = t1;
t1 = t1.next;
}
}
//end of first list, but second list has more nodes
//if the opposite happens, we will already have a sorted list
if(t1 == null && t2 != null){
p.next = t2;
}
//return the head node which has lower value since that will be the start of our final sorted list
if(headOne.value < headTwo.value){
return headOne;
}else
return headTwo;
}
}