Java Amazon questions - Combine two ascending order single linked list to single descending order single linked list with O(n) traverse

Hi Guys,

Recently i got interviewed by amazon and got below question in the programming round (First round).

Combine two ascending order single linked list to single descending order single linked list with O(n) traverse.


Input: L1 and L2

Output: L3

And also programmer wants the optimized solution for the above questions.

After discussing with many expert in data structure. Here i found the optimized solution.



Solution:

Algorithm:
Step 1: Initialize L3 Node and ;
Step 2: Traverse L1  and L2 Node by using the pointer.
Step 3: Initialize temp Node.
Step 4: compare L1 node and L2 and copy the less value to temp Node while traversing each node
Step 5:copy the temp node to the end of node L3.
Step 6:Increment pointer of node which is copied to the end of node L3.


Java Code:


public class ListNode {
Node node = null;
public ListNode() {

}

public ListNode(int val) {
node = new Node(val);
node.next = null;
}

// adding node to single linked list
public void addNode(int val) {
Node last = node;
while(last.next!=null) {
last = last.next;    
}
last.next = new Node(val);
last.next.next = null;
}


// traversing Node
public void traverse(){
Node first = node;
while(first != null) {
System.out.print(first.val+",");
first = first.next;
}
System.out.println();
}


// Here is the actual logic to merge and revers
public ListNode mergeAndReverse(Node L1, Node L2) {
Node L3 = null;
while(L1!=null || L2 !=null){
Node temp;
if(L1!=null && L2 !=null) {
if(L1.val <= L2.val) {
temp = new Node(L1.val);
L1 = L1.next;
} else {
temp = new Node(L2.val);
L2 = L2.next;
}
} else if(L1 !=null) {
temp = new Node(L1.val);
L1 = L1.next;
} else {
temp = new Node(L2.val);
L2 = L2.next;
}
if(L3 == null) {
L3 = temp;
temp.next = null;
} else {
temp.next = L3;
L3 = temp;
}
}
this.node = L3;
return this;
}
}

public class ListExample {

public static void main(String[] args) {

// TODO Auto-generated method stub

ListNode list1 =  new ListNode(1);

list1.addNode(4);

list1.addNode(7);

list1.addNode(13);

list1.addNode(19);

list1.traverse();

ListNode list2 =  new ListNode(1);

list2.addNode(2);

list2.addNode(5);

list2.addNode(17);

list2.addNode(22);

list2.addNode(28);

list2.traverse();

ListNode list3 = new ListNode();

ListNode res = list3.mergeAndReverse(list1.node, list2.node);

// list3.node = res;

res.traverse();

}

o/p:

1,4,7,13,19,

1,2,5,17,22,28,

28,22,19,17,13,7,5,4,2,1,1,

Click to Read more Data structure questions and answer

Please share this blog if you feel it is very helpfull