Good evening! Here's our prompt for today.
Write an algorithm to merge two sorted linked lists and return it as a new sorted list. The new list should be constructed by joining the nodes of the input lists.

You may assume the following node definition:
1public class Node {
2 int value;
3 Node next;
4
5 Node(int value) {
6 this.value = value;
7 this.next = null;
8 }
9
10 public static void main(String[] args) {
11 Node list1 = new Node(1);
12 list1.next = new Node(2);
13
14 System.out.println(list1.value + " -> " + list1.next.value);
15 }
16}
Write a method called mergeSortedLists
that would be invoked as such in the following example:
1// List 1: LinkedList<Integer> list1 = new LinkedList<>(Arrays.asList(1,5,6));
2// List 2: LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(2,3,4));
3
4LinkedList<Integer> mergedList = mergeSortedLists(list1, list2);
5// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
As you can see, the linked lists are merged in an ascending sorted order.
Constraints
- Length of the linked lists <=
100000
- The values in the nodes will be in the range
-1000000000
and1000000000
- Expected time complexity :
O(n)
- Expected space complexity :
O(n)
considering the call stack in recursion
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
113
​
import org.junit.Test;
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;
​
import static org.junit.Assert.*;
import org.junit.Before;
​
import java.util.ArrayList;
​
// solution
​
class Solution {
​
public static LinkedListNode mergeSortedLists(LinkedListNode head1, LinkedListNode head2) {
// fill in
// with solution
return null;
}
​
// print your findings using this function!
public static void log() {
System.out.println(MainTest.listToString(
mergeSortedLists(new LinkedListNode(0), new LinkedListNode(1)))
);
}
​
}
​
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Tired of reading? Watch this video explanation!
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

We'll now take you through what you need to know.
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.