We are Given two Linked Lists which are already sorted. We need to create a new linked list using these two linked lists and it is required to be in sorted order. One way we can do is to append second string in the first one and then will apply quick sort which will be having a time complexity of O(nlogn).
Can we do it in linear a time?
Yes, as it is given that both linked list is already sorted then we will just compare their head elements and will keep appending in a new linked list.
Java solution for the above question is below:
package askgif.linkedlist;
import java.util.Stack;
class ListNode{
public int data;
public ListNode next;
ListNode(int data){
this.data = data;
}
};
public class LinkedListNode {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(3);
ListNode node3 = new ListNode(5);
ListNode node4 = new ListNode(7);
ListNode node5 = new ListNode(9);
ListNode node6 = new ListNode(2);
ListNode node7 = new ListNode(4);
ListNode node8 = new ListNode(6);
ListNode node9 = new ListNode(8);
ListNode node10 = new ListNode(10);
ListNode node11 = new ListNode(11);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
node6.next = node7;
node7.next = node8;
node8.next = node9;
node9.next = node10;
node10.next = node11;
node11.next = null;
ListNode result = MergeLinkedList(node1,node6);
PrintLinkedList(result);
}
private static void PrintLinkedList(ListNode result) {
while(result != null) {
System.out.println(result.data);
result = result.next;
}
}
private static ListNode MergeLinkedList(ListNode node1, ListNode node2) {
ListNode result = null;
if(node1 == null)
return node2;
if(node2 == null)
return node1;
if(node1.data <= node2.data) {
result = node1;
result.next = MergeLinkedList(node1.next, node2);
}
else {
result = node2;
result.next = MergeLinkedList(node1, node2.next);
}
return result;
}
}
output:
1
2
3
4
5
6
7
8
9
10
11
Time Complexity: O(n)
Space Complexity: O(n) as we are using a new linked list for storage.
