Amazon Interview Question SDE1s
0of 0 votesMerge two sorted linked list
Team: Advertising
Country: United States
Interview Type: In-Person
Here it is:
public class MergeSortedLists {
static List<Integer> merge(List<Integer> list1, List<Integer> list2){
List<Integer> list=new LinkedList<Integer>();
int k1=0;
int k2=0;
while(k1<list1.size()&&k2<list2.size()){
if(list1.get(k1)<list2.get(k2)){
list.add(list1.get(k1++));
} else {
list.add(list2.get(k2++));
}
}
while(k1<list1.size()){
list.add(list1.get(k1++));
}
while(k2<list2.size()){
list.add(list2.get(k2++));
}
return list;
}
public static void main(String[] args){
List<Integer> list1=new LinkedList<Integer>();
List<Integer> list2=new LinkedList<Integer>();
list1.add(0);list1.add(2);list1.add(4);list1.add(6);
list2.add(1);list2.add(3);list2.add(5);
System.out.println(merge(list1,list2));
}
}
public Node mergeLists(Node head1, Node head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node result;
if (head1.value < head2.value) {
result = head1;
result.next = mergeLists(head1.next, head2);
} else {
result = head2;
result.next = mergeLists(head1, head2.next);
}
return result;
}
package com.shashi;
import java.util.LinkedList;
import java.util.List;
public class MergeSortedList {
public static void main(String []args)
{
List<Integer>list1=new LinkedList<Integer>();
list1.add(10);
list1.add(30);list1.add(60);list1.add(90);
list1.add(790);
List<Integer>list2=new LinkedList<Integer>();
list2.add(10);
list2.add(30);
list2.add(89);
list2.add(89);
list2.add(232);
list2.add(666);
mergeLists(list1,list2);
}
public static void mergeLists(List<Integer>l1,List<Integer>l2)
{
if(l1.size()==0 && l2.size()==0)
{
System.out.print("Emppty lists were given");
}
if(l1.size()==0)
{
System.out.print(l2);
return;
}
if(l2.size()==0)
{
System.out.print(l1);
return;
}
//now actual algorithm starts!!!!!!!
int index1=0,index2=0;
List<Integer> fill=new LinkedList<Integer>();
for(;index1<l1.size() && index2<l2.size();)
{
if(l1.get(index1)<l2.get(index2))
{
fill.add(l1.get(index1++));
if(index1==l1.size())
{
while(index2<l2.size())
{
fill.add(l2.get(index2++));
}
break;
}
}
else
{
fill.add(l2.get(index2++));
if(index2==l2.size())
{
while(index1<l1.size())
{
fill.add(l1.get(index1++));
}
break;
}
}
}
//print merged data
System.out.print(fill);
}
}
// Merged likedlist A & B into C
while A not empty or B not empty:
{
if A empty
remove first element from B and assign to variable
end if
else if B empty
remove first element from A and assign to variable
end else if
else if first element of A < first element of B:
remove first element from A and assign to variable
end else if
else
remove first element from B and assign to variable
insert element into C
}
node* merge1(node* root, node* root1)
{
node *start, *end,*i,*j,*prev1,*prev2;
i=root;
j=root1;
if(i->data > j->data)
{
while(j!=NULL && j->data < i->data)
{
prev2=j;
j=j->next;
}
prev2->next=i;
root=root1;
root1=j;
}
while(i!=NULL && j!=NULL)
{
if(i->data<j->data)
{
while( i!=NULL && j!=NULL && i->data < j->data)
{
prev1=i;
i=i->next;
}
while( i!=NULL && j!=NULL && i->data > j->data)
{
prev2=j;
j=j->next;
}
prev1->next=root1;
prev2->next=i;
root1=j;
}
}
return root;
}
Uses recursion and iterators, hence avoids calling get(int index) method which is inefficient.
public static List<Integer> merge(List<Integer> listA, List<Integer> listB)
{
if (listA == null) return listB;
if (listB == null) return listA;
final ListIterator<Integer> iterA = listA.listIterator(0);
final ListIterator<Integer> iterB = listB.listIterator(0);
final List<Integer> result = new LinkedList<Integer>();
merge(iterA, iterB, result);
return result;
}
private static void merge(ListIterator<Integer> iterA,
ListIterator<Integer> iterB,
List<Integer> result)
{
if (!iterA.hasNext())
{
while (iterB.hasNext()) { result.add(iterB.next()); }
return;
}
if (!iterB.hasNext())
{
while (iterA.hasNext()) {result.add(iterA.next()); }
return;
}
Integer a = iterA.next();
Integer b = iterB.next();
if (a < b)
{
result.add(a);
b = iterB.previous(); // rewind
}
else if (b < a)
{
result.add(b);
a = iterA.previous(); // rewind
}
else
{
result.add(a);
result.add(b);
}
merge(iterA, iterB, result);
}
def mergeSortedListsIteratively(l1head, l2head):
# empty head cases:
if not l1head:
return l2head
if not l2head:
return l1head
# initializing walkers
newHead = newListWalk = l2head
otherListHead = l1head
if l1head.value < l2head.value:
newHead = newListWalk = l1head
otherListHead = l2head
# merging lists
while otherListHead or newListWalk:
if otherListHead and newListWalk.next:
if otherListHead.value < newListWalk.next.value:
# append other, and place rest of new in other
tmp = newListWalk.next
newListWalk.next = otherListHead
otherListHead = tmp
newListWalk = newListWalk.next
elif otherListHead: # no newListWalk.next
newListWalk.next = otherListHead
return newHead
else: # no other list
return newHead
def mergeSortedListsIterativelySimpler(l1head, l2head):
# empty head cases:
if not l1head:
return l2head
if not l2head:
return l1head
# initializing walkers
newHead = newListWalk = l2head
otherListHead = l1head
if l1head.value < l2head.value:
newHead = newListWalk = l1head
otherListHead = l2head
# merging lists
while otherListHead and newListWalk.next:
if otherListHead.value < newListWalk.next.value:
# append other, and place rest of new in other
tmp = newListWalk.next
newListWalk.next = otherListHead
otherListHead = tmp
newListWalk = newListWalk.next
# appending end of other if reached end of newList
if otherListHead: # no newListWalk.next
newListWalk.next = otherListHead
return newHead
// -----------------------------------------------------------------------------
// Declare a NODE structure
// -----------------------------------------------------------------------------
typedef struct Node {
Node* next;
int data;
} NODE;
// -----------------------------------------------------------------------------
// Add a new node at the end of the list
// NOTE: Remember the special cases (the list is empty or has only one node)
// -----------------------------------------------------------------------------
void addEndNode(NODE** head, int value) {
NODE* newNode = createNewNode(value);
// SPECIAL CASE: The list is empty.
if (*head == NULL) {
*head = newNode;
}
// NORMAL CASE
else {
// In this normal case, we'll traverse till the end of the list
// and then add the new node there. The head pointer is still the same
// because we only change the tail of the list.
NODE* currentNode = *head;
// Go until we reach the end of the list
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}
// Add the new node to the end of the list
currentNode->next = newNode;
}
}
// -----------------------------------------------------------------------------
// Merge 2 shorted linked lists
// -----------------------------------------------------------------------------
NODE* mergeTwoShortedLinkedLists(NODE* head1, NODE* head2) {
NODE* head = NULL;
// Iterate each item of the two lists
// until we reach to the end of at least 1 lists
while (head1 != NULL && head2 != NULL) {
// If the current value of list1 is smaller than the current value of list2
// --> add the value of list 1 to the new list
if (head1->data <= head2->data) {
addEndNode(&head, head1->data);
// move to the next node in list 1, list 2 stays still
head1 = head1->next;
}
// same logic here
// if the current value of list2 is smaller than the current value of list1
// --> add the value of list 2 to the new list
else if (head2->data < head1->data) {
addEndNode(&head, head2->data);
// move to the next node in list 2, list 1 stays still
head2 = head2->next;
}
}
// If we reach this part of code, at least one of the list is now empty,
// all we need to do is to add the rest of the list that is still not empty
// to the new list
while (head1 != NULL) {
addEndNode(&head, head1->data);
head1 = head1->next;
}
while (head2 != NULL) {
addEndNode(&head, head2->data);
head2 = head2->next;
}
return head;
}
Iterative solution:
class ListNode {
public:
ListNode(int _data) : data(_data), next(nullptr) { };
ListNode* next;
int data;
};
ListNode* merge_ll(ListNode* a, ListNode* b)
{
if (nullptr == a) return b;
if (nullptr == b) return a;
auto d = (a->data < b->data) ? a : b;
auto s = (a == d) ? b : a;
ListNode* pd = nullptr;
while (nullptr != s && nullptr != d)
{
if (d->data < s->data)
{
pd = d;
d = d->next;
}
else
{
pd->next = s;
s = s->next;
pd->next->next = d;
pd = pd->next;
}
}
if (nullptr == d)
{
pd->next = s;
}
return (a->data < b->data) ? a : b;
}
Merging two Linked List without using recursion.
public void sortList(){ Link<Integer> current = list1; Link<Integer> buffer = list2; // if list2 data is smaller than list1 exchange the current and buffer pointers if(list2.data<list1.data) {current = list2; buffer = list1; } while(true){ if(buffer == null) break; if(current.data < buffer.data) { current = current.next; } else { Link<Integer> newNode = new Link<Integer>(buffer.data); newNode.next = current.next; current.next = newNode; current = current.next; buffer = buffer.next; } if(current.next==null) { current.next = buffer; break; } } }Changes are made in current pointer which references to list1.
- vrajendra.singh.mandloi October 05, 2014