## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 4 vote

Use two pointers. 1st pointer goes through list. Keep moving forward with 1st pointer as long as the next node is greater than the previously. As soon as the value hasn't increased, then you know you've found the front of the 2nd list.

Then start 2nd pointer at head, and merge the two lists like they were separate. Just make sure not to overlap the pointers.

Note: If the 1st pointer never finds a decreasing element, then every element in 2nd list was greater than every element in 1st list, so the lists when naturally sorted themselves.

O(n) runtime.

Comment hidden because of low score. Click to expand.
0

Not exactly sure what Matt meant by "merge" here. If he meant just joining the independent list pointers, then the logic does not work for all scenarios. Below is one example where it does not work:

3->6->9->1->2->4

Comment hidden because of low score. Click to expand.
0

@RK it will work even in your test case also
3->6->9->1->2->4
once you find a element which has value lower than previous which in your case is 1 then just merge the list starting at 1 and other starting at 3(ending at 9) as 2 separate sorted listed which can now be easily done in O(n) without any extra space.

``````//from jagat's post below
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}``````

Comment hidden because of low score. Click to expand.
1
of 3 vote

Here's the implementation of the algorithm given by Matt, which is just the Merge algorithm used by merge sort, with a preprocessing step before that to find the second sorted set.

``````void merge(node** list) {
if(list == null || *list == null)
return;
while(p2 != null) {
if(p1.data > p2.data) {
p1->next = null;
break;
}
p1 = p1->next;
p2 = p2->next;
}
if(p2 == null)
node* cur = (p1->data < p2->data ? p1 : p2);
*list = cur;
if(cur == p1)  p1 = p1->next;
else p2 = p2->next
}
while(true) {
if(p1 == null) {
cur->next = p2;
break;
}
else if(p2 == null) {
cur->next = p2;
break;
}
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Hey Jagat,

Just a slight modification to your code. In your while(true) block, please update cur to cur->next (only in second if else). The code sholud work fine then, I guess.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Can you explain how you do the merge please, like
ptr1=ptr1->next;

what does this do?

Comment hidden because of low score. Click to expand.
0

Maybe I name the variable in the wrong way.

first , I choose the right node which is ptr1 here.
Then , make the previous node's next (head->next) to ptr1
Third, update the previous node (head=ptr1)
at last, update ptr1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I knew this question sounds bs, the in place merge is not found yet how to do:

{{stackoverflow.com/questions/2126219/how-to-merge-two-sorted-integer-array-in-place-using-on-time-and-o1-space-co}}

Comment hidden because of low score. Click to expand.
0

It is hard to merge sorted "arrays" in place. But it's quite easy to merge linked list.

Comment hidden because of low score. Click to expand.
0

you are right, sorry missed on that

Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript:

``````function work(list){
while(current && current.next){
if(current.data > current.next.data){
secondHalf = current;
break;
}
current = current.next;
}
while(secondHalf.next){
var data = secondHalf.next.data;
var prev = {data:null, next:current};
while(current && current.data < data){
prev = current;
current = current.next;
}
var newNode = secondHalf.next;
prev.next = newNode;
secondHalf.next = newNode.next;
newNode.next =current;
if(!prev.data)
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
using namespace std;

struct Node
{
int val;
Node* next;
};

void PrintList(Node* root)
{
cout<<"\n";
while(root)
{
cout<< root->val<< " ";
root = root->next;
}
}

void BuildList(Node** root)
{
int arr[] = {1,2,3,4,5,1,2};

for(int i=0;i<7;i++)
{
Node* temp = new Node;
temp->val = arr[i];
temp->next = NULL;

if(*root)
}
else
{
}
}
}

void SortList(Node** root)
{
Node* second = *root;

while(second && second->next && second->val<second->next->val)
second = second->next;

second->next = NULL;

Node* Current=NULL, *Current2 = NULL;

{
{
if(Current)
{
Current=Current->next;
}
else

}
else
{
if(Current)
{
Current = Current->next;
}
else

}
}

{
Current = Current->next;
}
{
Current = Current->next;
}

Current->next = NULL;
*root = Current2;
}

int main()
{
Node* root = NULL;

BuildList(&root);
// PrintList(root);
SortList(&root);
PrintList(root);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

There is some bugs in my previous code . Here is tested code
Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;

while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
ptr2=ptr2->next;
}

while(ptr1!=NULL && ptr2!=NULL)
{
if(ptr1->data < ptr2->data)
{
{
ptr1=ptr1->next;
}
else
{
ptr1=ptr1->next;
}
}
else
{
{
ptr2=ptr2->next;
}
else
{
ptr2=ptr2->next;
}
}
}

if(ptr1==NULL)
{

}
if(ptr2==NULL)
{
}

return m;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
}
}

public class MergeList {

public static void main(String[] args) {
Node root = new Node(1);
root.next = new Node(2);
root.next.next = new Node(3);
root.next.next.next = new Node(4);
root.next.next.next.next = new Node(5);
root.next.next.next.next.next = new Node(1);
root.next.next.next.next.next.next = new Node(2);
//root.next.next.next.next.next.next.next = new Node(2);

Node temp = findMax(root);
//System.out.println(":::::" + temp.data);
Node temp1 = temp.next;
temp.next = null;

//System.out.println(" ");
}
}
static Node MergeLists(Node list1, Node list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}

if (list1.data <= list2.data) {
} else {
list2 = list1;
}
while(list1.next != null && list2 != null) {
if (list1.next.data <= list2.data) {
list1 = list1.next;
} else {
Node tmp = list1.next;
list1.next = list2;
list2 = tmp;
}
}
if (list1.next == null) {
list1.next = list2;
}
}

public static Node merge(Node h1, Node h2) {

Node h3 = new Node(0);
Node current = h3;

boolean isH1Left = false;
boolean isH2Left = false;

while (h1 != null || h2 != null) {
if (h1.data <= h2.data) {
current.next = h1;
h1 = h1.next;
} else {
current.next = h2;
h2 = h2.next;
}
current = current.next;

if (h2 == null && h1 != null) {
isH1Left = true;
break;
}

if (h1 == null && h2 != null) {
isH2Left = true;
break;
}
}

if (isH1Left) {
while (h1 != null) {
current.next = h1;
current = current.next;
h1 = h1.next;
}
}

if (isH2Left) {
while (h2 != null) {
current.next = h2;
current = current.next;
h2 = h2.next;
}
}

h3 = h3.next;

return h3;
}

public static Node findMax(Node max) {
while (max.next != null) {
if (max.data > max.next.data)
break;
max = max.next;
}

return max;
}
public static Node findMin(Node min) {

Node max = findMax(min);
if(max.next.data < min.data)
return min;
else
return max.next;

}
}

Comment hidden because of low score. Click to expand.
0

above code is correct but whats is complexity
anybody can explain

Comment hidden because of low score. Click to expand.
0
of 0 vote

explained it here - jasmeetsingh.net/wordpress/?p=55

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I get a in-place sort algorithm, is anyone can help me check this methods, if it does not work well, please tell me, with my thanks.
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;

void create_list(int *a, int n, LinkList *L) {
int i;
for(i = 0; i < n; i++) {
p->data = a[i];
p->next = NULL;
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
}
}

int _is_fisrt = 0;
while(p != NULL && q->data <= p->data) {
q = p;
p = p->next;
}

if(p == NULL) {
return ;
}
p_second_start = p;
q->next = NULL; // turn a list to two list
p = *L;
*L = NULL;
q = p_second_start;
while(p != NULL && q != NULL) {
if(p->data <= q->data) {
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
p = p ->next;
} else {
if(*L == NULL) {
*L = q;
} else {
temp->next = q;
}
temp = q;
q = q->next;
}
}
if(p != NULL) {
temp->next = p;
}
if(q != NULL) {
temp->next = q;
}
}

while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

void main() {
int a[] = {1, 5, 7, 9, 11, 2, 4, 6};
int n = sizeof(a) / sizeof(int);
create_list(a, n, &L);
print_list(L);
resort_list(&L);
print_list(L);
getchar();
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````#include<iostream>
using namespace std;

struct node
{
int k;
node *next;
};
node *l1=NULL,*l2=NULL,*l1_end=NULL;

node *create(int v)
{
node *n = new node;
n->k = v;
n->next = NULL;
return n;
}

void build(node *n)
{
else
{
while(m->next != NULL)
m = m->next;
m->next = n;
}
}

void show()
{
cout<<endl;
while(m!=NULL)
{
cout<<m->k<<"->";
m = m->next;
}
cout<<"NULL";
}

void sort()
{
if(l1->k <= l2->k)
{
l1 = l1->next;
}
else
{
l2 = l2->next;
}
while((l1 != l1_end) && (l2 != NULL))
{
if(l1->k <= l2->k)
{
m->next = l1;
m = m->next;
l1 = l1->next;
}
else
{
m->next = l2;
m = m->next;
l2 = l2->next;
}
}
while(l1 != l1_end)
{
m->next = l1;
m = m->next;
l1 = l1->next;
}
while(l2 != NULL)
{
m->next = l2;
m = m->next;
l2 = l2->next;
}
m->next = NULL;
}

void separate()
{
while(m!=NULL)
{
if((m->next != NULL) && (m->k > m->next->k))
{
l1_end = l2 = m->next;
sort();
return;
}
m = m->next;
}
cout<<"List is not compatible.";
}

int main()
{
int x;
char ch;
do
{
cout<<"Enter the key : ";
cin>>x;
build(create(x));
cout<<"Want to enter more (y/n) ? : ";
cin>>ch;
}while(ch == 'y');
show();
separate();
show();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void sortList(){
//first = points to the head,last=points to the beginning of second half

while(last.next.value>last.value){

last=last.next;
}
last=last.next;
//iterate over the second half of the list
while(count.next!=null){

//if element of second half of the list lies between the first value and its next
//then create a new node and add it in between them
if(count.value<first.next.value){
temp1.next=first.next;
first.next=temp1;
}else{
//increment first pointer till you get a value greater than the count pointer value
while(first.next.value<count.value)
first=first.next;
}

count=count.next;
}
//this part for the last node
if(count.next==null){

if(count.value<first.next.value){
temp1.next=first.next;
first.next=temp1;
}else{

while(first.next.value<count.value)
first=first.next;
temp1.next=first.next;
first.next=temp1;
}

}

temp.next=null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void sortList(){
//first = points to the head,last=points to the beginning of second half

while(last.next.value>last.value){

last=last.next;
}
last=last.next;
//iterate over the second half of the list
while(count.next!=null){

//if element of second half of the list lies between the first value and its next
//then create a new node and add it in between them
if(count.value<first.next.value){
temp1.next=first.next;
first.next=temp1;
}else{
//increment first pointer till you get a value greater than the count pointer value
while(first.next.value<count.value)
first=first.next;
}

count=count.next;
}
//this part for the last node
if(count.next==null){

if(count.value<first.next.value){
temp1.next=first.next;
first.next=temp1;
}else{

while(first.next.value<count.value)
first=first.next;
temp1.next=first.next;
first.next=temp1;
}

}

temp.next=null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello, could you check my implementation? To merge the lists what I do is:
1. Find the middle - where the second list starts and save this node
2. Compare the values of the start and the middle lists, if the value of the start is smaller than the value of the second list - > move the pointer of the first part to ne next element.
If the the other part is greater then:
1 step Create a new Node with the value of the element;
2 stepCreate a node - pointer to the next element of the second list;
3 step remove the node of the second list
4 step add the new node to the element before the current element of the first list
5 step move the current element of the second list to point to the next element - the node create in step 2

Here is the code in Java:

``````//2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
//Sample test case:
//Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
//Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11

public static void main(String[] args) {
List list = new List();
// the next sorted part of the list

System.out.println(list);
list.mergeLists();
System.out.println(list);
}

public static class List {
int count;

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(linkToStart.val + " - > ");
}
return sb.toString();
}

public void mergeLists() {

} else {
// copy node - I am not sure this is the best
Node n = new Node(linkToList2.val, null);

}
}
}

private Node findTheStartOfTheSecondPart() {
// find the starting point of the second sorted linked list

int tmpVal = -1;

break;
} else {
}
}
}

}

} else {
}
count++;
}

public void swapWithNext(int val1) {
return;
}
}
}

/**Add before by the node - compared by its value
* @param beforeNode
* @param node
*/
public void addBefore(Node beforeNode, Node node) {
}

/**
* Add before node - it adds after and then swap the values
* @param beforeNodeVal
* @param nodeVal
*/
public void addBefore(int beforeNodeVal, int nodeVal) {
swapWithNext(beforeNodeVal);
}

public void addAfter(int afterNodeVal, int nodeVal) {
Node afterNode = new Node(afterNodeVal, null);
Node node = new Node(nodeVal, null);
}

public void addAfter(Node afterNode, Node node) {
node.next = nextNode;
return;
}
}
}

/**
*
* @param val
*            the value of the element
*/
}

/**
*
* @param node
*/
else {
}
}
return this;
}

}

/**
*
*/
return null;
else {
}
}

/**
* Remove an element from the linked list - it searched the elements and
* removes after it finds one with the same value
*
* @param val
*            the value of the element which will be removed
* @return true if the element has been removed
*/
public boolean remove(int val) {
return remove(new Node(val, null));
}

public boolean remove(Node node) {
return false;
else {
return true;
}
}
}
return false;
}
}

/**
* @author lyubo Node of Linked List
*/
public static class Node {
int val;
Node next;

/**
* Constructor of the Node class
*
* @param val
* @param next
*/
public Node(int val, Node next) {
this.val = val;
this.next = next;
}

/*
*
* @see java.lang.Object#toString()
*/
public String toString() {
StringBuilder sb = new StringBuilder();
}
return sb.toString();
}

}
}``````

I will be very happy if someone can check my merge method and idea. Thanks :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Node merge2SortedHalfsOfLinkedLists(final Node head) {
while (p2 != null) {
if (p2.key < p1.key) {
break;
}
p1 = p1.next;
p2 = p2.next;
}
p1.next = null;
Node previous = null;
while (p1 != null) {
if (p2 != null) {
if (p2.key < p1.key) {
Node temp = p2.next;
p2.next = p1;
} else {
previous.next = p2;
p2 = p2.next;
}
p2 = temp;
}
} else {
break;
}
previous = p1;
p1 = p1.next;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

while (p2 != null) {
if (p2.key < p1.key) {
break;
}
p1 = p1.next;
p2 = p2.next;
}
p1.next = null;
Node previous = null;
while (p1 != null) {
if (p2 != null) {
if (p2.key < p1.key) {
Node temp = p2.next;
p2.next = p1;
} else {
previous.next = p2;
p2 = p2.next;
}
p2 = temp;
}
} else {
break;
}
previous = p1;
p1 = p1.next;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

working code with time complexity o(n);

``````#include <iostream>

using namespace std;

class list{
public:
int value;
list* next;
list* end;

list(int v){
value = v;
next = NULL;
end = this;
}

bool insert(int v){
if(end->next!=NULL){
list* t = new list(v);
t->next = this->next;
this->next = t;
return true;
}
list* nlist = new list(v);
end->next = nlist;
end = nlist;
return true;
}

void print(){
cout<<endl;
list* c = this;
while(c){
cout<<c->value<<" ";
c=c->next;
}
}
};

list* array2LL(int *a,int size){
if(size==0) return NULL;
list* start = new list(a[0]);
for(int i=1;i<size;i++){
start->insert(a[i]);
}
return start;
}

int main () {
int a[]={5,6,5,6,7,8,9,10};
list* start = array2LL(a,8);
start->print();
list *i,*j;
j=start;
while(j->next){
if(j->value > j->next->value){
break;
}
j=j->next;
}

list *p = new list(0);
list *pdmp;
pdmp = p;
i = new list(0);
i->next = start;
start = i;
p->next = j->next;
j->next = NULL;
list *cstart, *cend;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value >= p->next->value){
cstart = p->next;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value < p->next->value){
cend = p;
break;
}
p = p->next;
}
if(!p->next){
j = i->next;
i->next = cstart;
p->next = j;
start->next->print();
return 0;
}
pdmp->next = p->next;
p=pdmp;
j = i->next;
i->next = cstart;
cend->next = j;
}
i=i->next;
}//*/
if(!i->next){
i->next = p->next;
}
start->next->print();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the merge function in java......let mw know if there is a problem with it

``````static Node listmerge(Node l1,Node l2){

Node lista=l1;Node listb=l2;
int flag=0;
Node start=null;

if(flag==0)
{
if(l2.data>l1.data)
start=l1;
else
start=l2;
flag=1;
}

while(lista!=null && listb!=null){
if(lista.data<listb.data)
{
l1=lista;
while(l1.next!=null && l1.next.data<=listb.data)
{
l1=l1.next;
lista=lista.next;
}
if(l1.next!=null){
lista=l1.next;
l1.next=listb;}
else
lista=lista.next;
}
else
{
l2=listb;
while(l2.next!=null && l2.next.data<=lista.data)
{
l2=l2.next;
listb=listb.next;
}
if(l2.next!=null){
listb=l2.next;
l2.next=lista;}
else
listb=listb.next;
}
}

//adding the remainder of other list
if(l1.next==null && l2.next!=null)
l1.next=listb;
if(l2.next==null && l1.next!=null)
l2.next=lista;

return start;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {

private final int val;
private Node next;

Node(int val) {
this.val = val;
}

public int getVal() {
return val;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

@Override
public String toString() {
return val + "->" + (getNext() == null ? "null" : getNext().val);
}
}

public class Sort {

public Node mergeSortedList(Node root) {
Node r = new Node(0);
r.setNext(root);

Node p1 = r;
Node p2 = findLastOfFirst(root);

while (p2.getNext() != null) {
if(p1.getNext().getVal() <= p2.getNext().getVal()) {
p1 = p1.getNext();
} else {
Node temp = p1.getNext();
Node temp2 = p2.getNext().getNext();

p1.setNext(p2.getNext());

p2.getNext().setNext(temp);
p2.setNext(temp2);
}
}

return r.getNext();
}

Node findLastOfFirst(Node root) {
while(root.getVal() < root.getNext().getVal()) {
root = root.getNext();
if(root == null) {
throw new IllegalArgumentException("Can't find the second list");
}
}
return root;
}
}

public class SortTest {

private Sort sort;

@Before
public void setUp() throws Exception {
sort = new Sort();
}

@Test
public void test1() {
Node list = createList(1, 2, 3, 4, 5, 1, 2);
assertListEquals(list, 1,2,3,4,5,1,2);

list = sort.mergeSortedList(list);

assertListEquals(list, 1,1,2,2,3,4,5);
}

@Test
public void test2() {
Node list = createList(1, 5, 7, 9, 11, 2, 4, 6);

list = sort.mergeSortedList(list);

assertListEquals(list, 1,2,4,5,6,7,9,11);
}

@Test
public void test3() {
Node list = createList(4, 5, 7, 9, 11, 1, 2, 3);

list = sort.mergeSortedList(list);
print(list);

assertListEquals(list, 1,2,3,4,5,7,9,11);
}

@Test
public void testFindSecond() throws Exception {
Node list = createList(5, 6, 7, 8, 9, 3, 4);
Node second = sort.findLastOfFirst(list);
assertEquals(9, second.getVal());
}

private static Node createList(int... values) {
Node root = null;
Node current = null;
for(int value : values) {
Node node = new Node(value);
if(current != null) {
current.setNext(node);
}
current = node;
if(root == null) {
root = current;
}
}
return root;
}

private void print(Node list) {
while(list != null) {
System.out.print(list.getVal());
System.out.print(" ");
list = list.getNext();
}
System.out.println();
}

private void assertListEquals(Node list, int... values) {
for (int i = 0, valuesLength = values.length; i < valuesLength; i++) {
int value = values[i];
if (list == null) {
fail();
}
assertEquals("Failed at ["+i+"] element: ", value, list.getVal());
list = list.getNext();
}
if(list != null) {
fail();
}
}

}

Comment hidden because of low score. Click to expand.
0

Again, with indents:

package merge1;

/**
* User: igor
* Date: 25.01.13
* Time: 2:07
*/
public class Node {

private final int val;
private Node next;

Node(int val) {
this.val = val;
}

public int getVal() {
return val;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

@Override
public String toString() {
return val + "->" + (getNext() == null ? "null" : getNext().val);
}
}

public class Sort {

public Node mergeSortedList(Node root) {
Node r = new Node(0);
r.setNext(root);

Node p1 = r;
Node p2 = findLastOfFirst(root);

while (p2.getNext() != null) {
if (p1.getNext().getVal() <= p2.getNext().getVal()) {
p1 = p1.getNext();
} else {
Node temp = p1.getNext();
Node temp2 = p2.getNext().getNext();

p1.setNext(p2.getNext());

p2.getNext().setNext(temp);
p2.setNext(temp2);
}
}

return r.getNext();
}

Node findLastOfFirst(Node root) {
while (root.getVal() < root.getNext().getVal()) {
root = root.getNext();
if (root == null) {
throw new IllegalArgumentException("Can't find the second list");
}
}
return root;
}
}

public class SortTest {

private Sort sort;

@Before
public void setUp() throws Exception {
sort = new Sort();
}

@Test
public void test1() {
Node list = createList(1, 2, 3, 4, 5, 1, 2);
assertListEquals(list, 1, 2, 3, 4, 5, 1, 2);

list = sort.mergeSortedList(list);

assertListEquals(list, 1, 1, 2, 2, 3, 4, 5);
}

@Test
public void test2() {
Node list = createList(1, 5, 7, 9, 11, 2, 4, 6);

list = sort.mergeSortedList(list);

assertListEquals(list, 1, 2, 4, 5, 6, 7, 9, 11);
}

@Test
public void test3() {
Node list = createList(4, 5, 7, 9, 11, 1, 2, 3);

list = sort.mergeSortedList(list);
print(list);

assertListEquals(list, 1, 2, 3, 4, 5, 7, 9, 11);
}

@Test
public void testFindSecond() throws Exception {
Node list = createList(5, 6, 7, 8, 9, 3, 4);
Node second = sort.findLastOfFirst(list);
assertEquals(9, second.getVal());
}

private static Node createList(int... values) {
Node root = null;
Node current = null;
for (int value : values) {
Node node = new Node(value);
if (current != null) {
current.setNext(node);
}
current = node;
if (root == null) {
root = current;
}
}
return root;
}

private void print(Node list) {
while (list != null) {
System.out.print(list.getVal());
System.out.print(" ");
list = list.getNext();
}
System.out.println();
}

private void assertListEquals(Node list, int... values) {
for (int i = 0, valuesLength = values.length; i < valuesLength; i++) {
int value = values[i];
if (list == null) {
fail();
}
assertEquals("Failed at [" + i + "] element: ", value, list.getVal());
list = list.getNext();
}
if (list != null) {
fail();
}
}

}

Comment hidden because of low score. Click to expand.
0

Damn! How do you do the indentation?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class CCID15145684{
for(int i=0;i < ll.size();i++){
System.out.print(ll.get(i) + ", ");
}
System.out.println();
}

// List 1: 1->2->3->4->5->1->2;
// List 2: 1->5->7->9->11->2->4->6;
}

// List 1: 1->2->3->4->5->1->2;
int ip = -1;
for(int i=1; i< ll.size(); i++){
if(ll.get(i-1) > ll.get(i)){
ip = i;
break;
}
}

System.out.println("Inflexion point = " + ll.get(ip));
int s1 = 0; int e1 = ip;
int s2 = ip; int e2 = ll.size();

while( (s1 < e1) && (s2 < e2)){
if(ll.get(s1) > ll.get(s2)){
s2++;
}else{
s1++;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void sort(struct node **base)
{
struct node *temp,*m,*n,*r;
temp=*base;
m=*base;

if(m->data > n->data)
{
r=n;
*base=r;
m=*base;
}
while(m != n && n != NULL)
{
{
r=n;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdlib.h>
#include <stdio.h>
{
int value;
};
static int count=0;
main()
{
int ind;
scanf("%d",&ind);

}

node *local,*sortedList;
int i;

{
else {
local=sortedList->next;
return(sortedList);
}
}
else {
/*............Look for starting of 2nd starting sorted list..........*/

next_ptr=next_ptr->next;
}
local_nexPtr= next_ptr;
//printlist(next_ptr);
{
next_ptr= next_ptr->next;
}
else{
}
while ( (local_head != local_nexPtr) && (next_ptr != NULL))
{
{
next_ptr= next_ptr->next;
}
else{
}
}
if(( local_head !=local_nexPtr) && (next_ptr == NULL)){

}
}
if(( local_head ==local_nexPtr) && (next_ptr != NULL)){

while ( (next_ptr != NULL)){
next_ptr= next_ptr->next;
}
}

}
}
int i;
}

}
int n;
node *prenode;

printf("enter the value ( typ 9999 to end the list)\n");

}
else

return;
}
int i;
{
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just an implementation of Matt's algo

Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;

while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
}
while(ptr1->next!=NULL && ptr2->next!=NULL)
{
if(ptr1->data < ptr2->data)
{
{
ptr1=ptr1->next;
}
else
{
ptr1=ptr1->next;
}
}
else
{
{
ptr1=ptr2->next;
}
else
{
ptr2=ptr2->next;
}
}
}

if(ptr1->next==NULL)
{
ptr1->next=ptr2;

}
if(ptr2->next==NULL)
{
ptr2->next=ptr1;
}

return m;
}

Comment hidden because of low score. Click to expand.
0

hi Peng , can you please help me to know complexity .. i think it is O(m*n) where m = number of elements in the first list and n = number of elements in the 2nd list .. is that correct ?

Comment hidden because of low score. Click to expand.
0

@hint
No, it's just O(n) where n is the length of the linked list. The first loop finds the start of the second sorted set and the second loop performs the merge and touches each node just once. If you notice, the loops are not nested. They're O(n) independently and hence O(n) overall.

Edit: Peng's loop that is supposed to find the second sorted set is buggy. It doesn't shift the pointers to the next nodes after it has examined a pair of nodes.

Comment hidden because of low score. Click to expand.
0

Thanks Jagat

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package string;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
*
* @author IYER HOME
*/
public class listmerge {

public void createList(List<Integer> list,int length)
{
int prev=0;
List list1=new ArrayList();
List list2=new ArrayList();
for(int i=0;i<length;i++)
{

int next=list.get(i);
if(prev < next)
{
prev=next;

}
else
{
}

}

System.out.println("List1 values"+list1);
System.out.println("List2 values"+list2);
mergeList(list1,list2);
}

public void mergeList(List list1,List list2)
{
List sortedList=new ArrayList();
System.out.println(sortedList);

int i=0;
int j=0;
while(i<list1.size()&&j<list2.size())
{
if((Integer)list1.get(i)<(Integer)list2.get(j))
{
i++;
}
else
{
j++;
}
}
while(i<list1.size())
{
i++;
}
while(j<list2.size())
{
j++;
}

System.out.println(sortedList);
}

public static void main(String args[]) throws IOException
{
List<Integer> list=new ArrayList<Integer>();
int length=Integer.parseInt(val);
int value_list;
for(int i=0;i<length;i++)
{

}

System.out.println(list);
listmerge merge=new listmerge();
merge.createList(list,length);
}

}

Comment hidden because of low score. Click to expand.
0

You can't use extra space....as mentioned in the question

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why don't we just use BST logic here.
Create a BST and do Inorder travesal.

Comment hidden because of low score. Click to expand.
0

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.