Amazon Interview Question for SDE1s


Team: TCS
Country: India
Interview Type: Written Test




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

Check if the list is null or it is sorted, if yes, return.
Otherwise, have a pointer starting from the beginning, iterate until find the beginning of the second half, call it p2. Have p1 pointing at the beginning of the array, merge them to a new linkedlist by manipulating the pointers.

- maillist.danielyin September 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

contd... remember to find the node which is just before the beginning of the second half in order to remove the node from second half and insert in first half.

[assumption: if the linked list is singly linked list]

Enjoy coding!!!

- siva September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well it`s not about inserting the second half into the first half, we are merging them to a new head pointer, which is easier than inserting into the first half.

- maillist.danielyin September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You shouldn't be using a buffer. It says don't use extra space !!

- Yusuf March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Implementation of same logic ............





struct node *merge(struct node *a,struct node *b ){

if(a==NULL) return b;
else if(b==NULL) return a;
struct node *result=NULL;

if(a->data <= b->data){
result=a;
result->next=merge(a->next,b);
}else{

result=b;
result->next=merge(a,b->next);
}

return result;
}

struct node * sort(struct node *head){

struct node *t=head;
while(t->next!=NULL && t->data <= t->next->data ){
t=t->next;
}
struct node *next=t->next;
t->next=NULL;

head= merge(head,next);
return head;
}

- Anonymous April 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

struct node *sortlist(struct node *root) {

	struct node *middle = NULL, *later = NULL, *parent = NULL, *pwalk2 = NULL;
	if(NULL == root) {
		return root;
	}
	
	middle = root;
	while(middle->next) {
		
		if(middle->data <= middle->next->data)
			middle = middle->next;
		else 
			break;
	}
	
	if(middle->next) {
	 	
	 	
	 	later = middle->next;
		
		/*special case when node goes on top*/
		if(later->data < root->data) {
			if(later->next != NULL)
				middle->next = later->next;
			else {
				middle->next = NULL;
				later->next = middle;
				return later;
			}
			later->next = root;	
			root = later;
			
		}
		
		/*goes in somewhere middle*/
		parent = root;
		while(middle->next) {
			pwalk2 = parent->next;
			while(pwalk2 != middle->next) {
				
				
				later = middle->next;
				if(later->data <= pwalk2->data) {
			
					if(later->next != NULL)
						middle->next = later->next;
					else 
						middle->next = NULL;			
			
					parent->next = later;
					later->next = pwalk2;
					break;
				}
				parent = pwalk2;
				pwalk2 = pwalk2->next;
			}
		
		}
		return root;
	
	} else {
	
		return root;
	}

}

- joyboyhardik September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1)As said by joyboyhardik break the list when the value is less than the previous value.
2)Apply the sorting algorithm on second list .
3)Merge both the list

- RashmiBs September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static Node merge(Node n1, Node n2) {
    if (n1 == null) return n2;
    if (n2 == null) return n1;

    if (n1.value < n2.value) {
        n1.next = merge(n1.next, n2);
        return n1;
    } else {
        n2.next = merge(n2.next, n1);
        return n2;
    }
}

- Deepak September 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome!!

- sagar October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

some modification to your code:
if (n1 == null)
{
n2->next=NULL;
return n2;
}
if (n2 == null)
{
n1->next = NULL;
return n1;
}

- john November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Link {
	
	public List<Integer> ll(List<Integer> l1, List<Integer> l2){
		List <Integer> l3 = new LinkedList<>();
		if(l1.size()==0 || l2.size()==0) return null;
		l3.addAll(l1);
		l3.addAll(l2);
		Collections.sort(l3);
		System.out.println(l3);		
		return l3;
	}

	public static void main(String[] args) {
		Link ll2 = new Link();
		LinkedList<Integer> l2 = new LinkedList <Integer>(); 
		LinkedList<Integer> l1 = new LinkedList <Integer>(); 
		l1.add(1);
		l1.add(5);
		l1.add(7);
		l1.add(9);
		l2.add(11);
		l1.add(1);
		l2.add(2);
		l2.add(4);
		l2.add(6);
		ll2.ll(l1, l2);
		
	}

}

- Anonymous September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Link {

public List<Integer> ll(List<Integer> l1, List<Integer> l2){
List <Integer> l3 = new LinkedList<>();
if(l1.size()==0 || l2.size()==0) return null;
l3.addAll(l1);
l3.addAll(l2);
Collections.sort(l3);
System.out.println(l3);
return l3;
}

public static void main(String[] args) {
Link ll2 = new Link();
LinkedList<Integer> l2 = new LinkedList <Integer>();
LinkedList<Integer> l1 = new LinkedList <Integer>();
l1.add(1);
l1.add(5);
l1.add(7);
l1.add(9);
l2.add(11);
l1.add(1);
l2.add(2);
l2.add(4);
l2.add(6);
ll2.ll(l1, l2);

}

}

- revanth September 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

// Solution using  C#
 public void Merge2SortSingleList(Node startNode )
        {
            Node head = startNode;
            int count = 1;

            while ( head.data < head.next.data ) 
            {
                head = head.next;
                count++;
            }

            if (head.next != null)
            {
                Node pervious = null;
                Node split = head;
                head = head.next;

                while (count > 1 && head.next != null)
                {
                    if ( startNode.data < head.data)
                    {
                        pervious = startNode;
                        startNode = startNode.next;
                        count--;
                    }
                    else if ( startNode.data => head.data)
                    {
                        split.next = head.next;
                        pervious.next = head;
                        head.next = startNode;
                        pervious = head;
                        head = split.next;
                    }
                }
                
                if (head.next == null)
                {
                    if  (startNode.data => head.data)
                    {
                        split.next = head.next;
                        pervious.next = head;
                        head.next = startNode;
                    }
                }
            }
        }

- Nalini Ambhore October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Small correction at line 16 in while loop, count should be greater than 0 i.e while (count > 0 && head.next != null)

- Nalini Ambhore October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The solution is in Java ....

1. First split the list into two separate sorted lists (List1, List2)
2. Merge the lists to return single sorted list

public Node splitAndMerge2SortedLists(Node list){
		//split the list when current node's item value is greater than the next node's item
		Node current = list;
		Node sec_list = null;
		while(current != null && current.next != null){
			if(current.item > current.next.item){
				sec_list = current.next;
				current.next = null;
				break;
			}
			current = current.next;
		}
		
		//merge two sorted lists now
		//create a fake node
		Node temp = new Node(0);
		Node p = temp;
		while(list != null && sec_list != null){
			if(list.item <= sec_list.item){
				p.next = list;
				list = list.next;
			}else{
				p.next = sec_list;
				sec_list = sec_list.next;
			}
			p = p.next;
		}
		//set the last node
		if(list != null){
			p.next = list;
		}if(sec_list != null){
			p.next = sec_list;
		}
		//returns the next node to the fake node (0) which is already sorted
		return temp.next;

}

- Dibyendu March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So based on the example you give, they are not exactly first half and second half. Should be the first part and second part.

- maillist.danielyin September 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a variation of the merging two sorted linked lists problem. You would need to traverse the linked list till the point where the next node value is greater than the current node value. By doing this you can figure out the starting of two sorted linked list. Then merge the two sorted linked list.

- Vs September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, was this question in an online assessment test?

- Arpit September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Writing my solution in Java

Node mergePartlySortedLinkedList(Node root){
 	Node list1Node = root;
 	Node list2Node = root.next;
 	while(list2Node != null && list2Node.val>=list1Node.val){
 		list1Node = list2Node;
 		list2Node = list2Node.next;
 	}
 	if(list2Node == null)
 		return root;
 		
 	list1Node.next == Null;
 	list1Node = root;
 	Node newroot;
 	if(list1Node.val<=list2Node.val){
 		newroot = list1Node;
 		list1Node = list1Node.next;
 	}else{
 		newroot = list2Node;
 		list2Node = list2Node.next;
 	}
 	Node curNode = newroot;
 	
 	while(lis1Node!=null || list2Node!=null){
 		if(list1Node != null && (list2Node == null || list1Node.val <= list2Node.val)){
 			currNode.next = list1Node;
 			list1Node = list1Node.next;
 		}else{
 			currNode.next = list2Node;
 			list2Node = list2Node.next;
 		}
 		currNode = currNode.next;
 	}
 	currNode.next = null;
 	
 	return newroot;
 }

- Anonymous September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your first line uses at least 32bits to store the address of root, which violates the requirement do not use any extra space.

- wxh September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep in mind the question says do not use any extra space, which means even an extra single bit is not allowed.

How can that be possible?

- wxh September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution proposal in C++:

node* sortLists(node* list)
{
	node* ptr1=list;
	node* ptr2=list;
	
	while((ptr1->data <= ptr1->next->data) && ptr1->next->next!=NULL)
	{
		ptr1=ptr1->next;
	}
	
	node* aux=ptr1;
	ptr1=ptr1->next;
	aux->next=NULL;
	
	node* new_list=NULL;
	
	while(ptr1!=NULL && ptr2!=NULL)
	{
		if(ptr2->data<=ptr1->data)
		{
			new_list=insertData(ptr2->data,new_list);
			ptr2=ptr2->next;
		}
		else
		{
			new_list=insertData(ptr1->data,new_list);
			ptr1=ptr1->next;
		}
	}
	if(ptr1==NULL)
	{
		while(ptr2!=NULL)
		{
			new_list=insertData(ptr2->data,new_list);
			ptr2=ptr2->next;
		}
	}
	else
	{
		while(ptr1!=NULL)
		{
			new_list=insertData(ptr1->data,new_list);
			ptr1=ptr1->next;
		}
	}
	return new_list;
}

- NL September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Break the linked list when the value is less than the previous value.
2. Now you have two linked lists, one sorted and other sorted in reverse order.
3. Reverse the second linked list which is sorted in reverse order.
4. Merge the sorted linked lists

- Srikanth September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int val;
struct node* next;
};

struct node* create_node(int value)
{
struct node *ptr;
ptr=(struct node*)malloc(sizeof(struct node));
ptr->val=value ;
ptr->next=NULL;
}
void display(struct node* head)
{
while(head!=NULL)
{
printf("%d ",head->val);
head=head->next;
}
printf("\n");
}
struct node * merge(struct node *ptr1,struct node *ptr2)
{
struct node* result=NULL;
if(ptr1==NULL)
return ptr2;
else if(ptr2==NULL)
return ptr1;
if(ptr1->val < ptr2->val)
{
result=ptr1;
result->next=merge(ptr1->next,ptr2);

}
else
{
result=ptr2;
result->next=merge(ptr1,ptr2->next);
}
return result;
}
sort(struct node **head)
{
if(*head==NULL||(*head)->next==NULL)
return ;
struct node *ptr1=*head;
struct node* prv=ptr1;
struct node* ptr2;
ptr1=ptr1->next;
while(prv->val<ptr1->val)
{
prv=ptr1;
if(ptr1->next==NULL)
return;
ptr1=ptr1->next;
}
ptr2=ptr1;
prv->next=NULL;

*head=merge(*head,ptr2);
}


int main()
{
struct node *head;
head=create_node(1);
head->next=create_node(2);
head->next->next=create_node(3);
head->next->next->next=create_node(4);
head->next->next->next->next=create_node(5);
head->next->next->next->next->next=create_node(1);
head->next->next->next->next->next->next=create_node(2);
//display(head);
sort(&head);
display(head);

}

- nileshagarwal10 September 28, 2013 | Flag Reply
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 add(struct node** p,int n)
{
        struct node* temp= new node;
        //struct node* temp =
        //              (struct node*) malloc(sizeof(struct node));
        temp->val=n;
        temp->next=NULL;
        if(*p==NULL)
        {
                *p=temp;
        }
        else
        {
                struct node* mover=*p;
                while(mover->next!=NULL)
                        mover=mover->next;
                mover->next=temp;
        }
}
void display(struct node* p)
{
        struct node*temp=p;
        cout<<endl;
        while(temp->next!=NULL)
        {
                cout<<temp->val<<" --> ";
                temp=temp->next;
        }
        cout<<temp->val<<" --> NULL"<<endl;
}
void mergelist(struct node**p)
{
        struct node*temp=*p;
        while(temp->next->val > temp->val)
                temp=temp->next;
        struct node*ptr1,*ptr2,*ptr1_prev,*ptr2_prev;
        ptr1=*p;
        ptr1_prev=NULL;
        ptr2=temp->next;
        ptr2_prev=NULL;
        temp->next=NULL;
        while(ptr1!=NULL && ptr2!=NULL)
        {
                if(ptr1->val > ptr2->val)
                {
                        if(ptr1_prev==NULL && ptr2_prev ==NULL)
                        {
                                ptr2_prev=ptr2;
                                ptr2=ptr2->next;
                                ptr2_prev->next=*p;
                                *p=ptr2_prev;
                                ptr1_prev=*p;
                                ptr2_prev=NULL;
                        }
                        else
                        {
                                ptr2_prev=ptr2;
                                ptr2=ptr2->next;
                                ptr1_prev->next=ptr2_prev;
                                ptr2_prev->next=ptr1;
                                ptr1_prev=ptr2_prev;
                                ptr2_prev=NULL;
                        }
                }
                else
                {
                        ptr1_prev=ptr1;
                        ptr1=ptr1->next;
                }

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

}


int main()
{
        struct node *p=NULL;
        int n;
        cout<<"\nEnter space separated input(-1 at the end of input)\n\n";
        while(cin>>n)
        {
                if(n==-1)
                        break;
                else
                        add(&p,n);
        }
        cout<<"\nInput\n";
        display(p);
        mergelist(&p);
        cout<<"\nOutput\n";
        display(p);
}

- Harjit Singh September 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <malloc.h>

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

void create_linklist(struct node **, int);
void display(struct node *);
void sort_linklist(struct node **);

int main() {
struct node *p = NULL;
create_linklist(&p, 2);
create_linklist(&p, 1);
create_linklist(&p, 5);
create_linklist(&p, 4);
create_linklist(&p, 3);
create_linklist(&p, 2);
create_linklist(&p, 1);
//create_linklist(&p, 1);
display(p);
printf("\n");
sort_linklist(&p);
display(p);
return 0;
}

void create_linklist(struct node **q, int num) {
struct node *temp = (struct node*) (malloc(sizeof(struct node)));
temp->val = num;
temp->next = *q;
*q = temp;
}

void display(struct node *q) {
while (q) {
printf("%d\t", q->val);
q = q->next;
}
}

void sort_linklist(struct node **q) {
if (!(*q))
return;
else {
struct node *temp1 = *q;
struct node *temp2 = *q;
struct node *temp3;
while ((temp1->next) && (temp1->val < temp1->next->val))
temp1 = temp1->next;

if (!(temp1->next))
return;
*q=temp2;
while (temp1->next)
{
if (temp1->next->val < temp2->val)
{
temp3 = temp1->next;
temp1->next = temp3->next;
temp3->next = temp2;
temp2 = temp3;
*q=temp3;
}
else
{
while (temp2->next->val < temp1->next->val)
temp2 = temp2->next;
temp3 = temp1->next;
temp1->next = temp3->next;
temp3->next = temp2->next;
temp2->next = temp3;
temp2 = temp3;
}
}
}
}

- Anonymous October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <malloc.h>

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

void create_linklist(struct node **, int);
void display(struct node *);
void sort_linklist(struct node **);

int main() {
	struct node *p = NULL;
	create_linklist(&p, 2);
	create_linklist(&p, 1);
	create_linklist(&p, 5);
	create_linklist(&p, 4);
	create_linklist(&p, 3);
	create_linklist(&p, 2);
	create_linklist(&p, 1);
	//create_linklist(&p, 1);
	display(p);
	printf("\n");
	sort_linklist(&p);
	display(p);
	return 0;
}

void create_linklist(struct node **q, int num) {
	struct node *temp = (struct node*) (malloc(sizeof(struct node)));
	temp->val = num;
	temp->next = *q;
	*q = temp;
}

void display(struct node *q) {
	while (q) {
		printf("%d\t", q->val);
		q = q->next;
	}
}

void sort_linklist(struct node **q) {
	if (!(*q))
		return;
	else {
		struct node *temp1 = *q;
		struct node *temp2 = *q;
		struct node *temp3;
		while ((temp1->next) && (temp1->val < temp1->next->val))
			temp1 = temp1->next;

		if (!(temp1->next))
			return;
		*q=temp2;
		while (temp1->next)
		 {
			if (temp1->next->val < temp2->val)
			 {
				temp3 = temp1->next;
				temp1->next = temp3->next;
				temp3->next = temp2;
				temp2 = temp3;
				*q=temp3;
			 }
			else
			 {
				while (temp2->next->val < temp1->next->val)
				temp2 = temp2->next;
				temp3 = temp1->next;
				temp1->next = temp3->next;
				temp3->next = temp2->next;
				temp2->next = temp3;
				temp2 = temp3;
			}
		}
	}
}

- Lalit October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void mergeLinklist(Linklist l1,Linklist l2)
{
lnode current =l1.root;
lnode wait;
while (current.data < current.link.data)
{
current = current.link;
}
lnode start=l1.root;
current=current.link;
wait=current;
while (start!=null && current!=null)
{

if (start.data < current.data)
{
l2.insert(start.data);
start= start.link;
}
else
{
l2.insert(current.data);
current = current.link;
}
}


while (start!=wait)
{
l2.insert(start.data);
start= start.link;
}

while (current!=null)
{
l2.insert(current.data);
current = current.link;
}
}

- GT1 October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My implementation in C.

#include <stdio.h>
#include <stdlib.h>

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

struct node* createNode(int val) {
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

struct node *sortlist(struct node *root) {
    if(root == NULL || root->next == NULL)
        return root;
    struct node *ptrFront=root, *ptrBack=NULL, *ptr=root;
    struct node *HEAD = createNode(-1);
    while(ptr->next != NULL) {
        if(ptr->val > ptr->next->val) {
            ptrBack = ptr->next;
            ptr->next = NULL;
            break;
        }
        ptr = ptr->next;
    }
    ptr = HEAD;    
    while(ptrFront != NULL && ptrBack != NULL) {
        if(ptrFront->val > ptrBack->val) {
            ptr->next = ptrBack;
            ptrBack = ptrBack->next;
        } else {
            ptr->next = ptrFront;
            ptrFront = ptrFront->next;
        }       
        
        ptr = ptr->next;
    }
    while(ptrFront != NULL) {
        ptr->next = ptrFront;
        ptrFront = ptrFront->next; 
        ptr = ptr->next;
    }
    while(ptrBack != NULL) {
        ptr->next = ptrBack;
        ptrBack = ptrBack->next;
        ptr = ptr->next;
    }
    HEAD = HEAD->next;
    return HEAD;
}

void printList(struct node* HEAD) {
    struct node* ptr = HEAD;
    while(ptr != NULL) {
        printf("%d ", ptr->val);
        ptr = ptr->next;
    }
    return;
}

int main()
{
    struct node* root = createNode(1);
    root->next = createNode(2);
    root->next->next = createNode(3);
    root->next->next->next = createNode(1);
    root->next->next->next->next = createNode(2);
    struct node* HEAD = sortlist(root);
    printList(HEAD);
    return 0;
}

- sudhanshu97gupta October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node* sortList(struct node* head)
{
        struct node* curr = head;
        while(curr->next)
        {
                if (curr->next->data >= curr->data)
                curr = curr->next;
                else
                break;
        }

        struct node* begin = curr->next;                // begin ->  first element of second list
        struct node* state = head;                      // state ->  element which will be compared next from first list
        struct node* prev = NULL;                       // prev  ->  element just before state in the linked list
        while(state->next)
                                        {
                                                if ( state == begin )
                                                        {
                                                                begin = begin->next;

                                                        }
                                                else{
                                                if (begin->data >= state->data)
                                                        {
                                                                prev = state;
                                                                state=state->next;
                                                        }
                                                else    {
                                                curr->next  = begin->next;
                                                if (prev == NULL)
                                                        head = begin;
                                                else
                                                        prev->next = begin;
                                                begin->next = state;
                                                prev = begin;
                                                begin = curr->next;
                                                        }
                                                }
                                                if (begin == NULL)
                                                        break;
                                        }

        return head;
}

- Anonymous November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node* sortList(struct node* head)
{
        struct node* curr = head;
        while(curr->next)
        {
                if (curr->next->data >= curr->data)
                curr = curr->next;
                else
                break;
        }

        struct node* begin = curr->next;                // begin ->  first element of second list
        struct node* state = head;                      // state ->  element which will be compared next from first list
        struct node* prev = NULL;                       // prev  ->  element just before state in the linked list
        while(state->next)
                                        {
                                                if ( state == begin )
                                                        {
                                                                begin = begin->next;

                                                        }
                                                else{
                                                if (begin->data >= state->data)
                                                        {
                                                                prev = state;
                                                                state=state->next;
                                                        }
                                                else    {
                                                curr->next  = begin->next;
                                                if (prev == NULL)
                                                        head = begin;
                                                else
                                                        prev->next = begin;
                                                begin->next = state;
                                                prev = begin;
                                                begin = curr->next;
                                                        }
                                                }
                                                if (begin == NULL)
                                                        break;
                                        }

        return head;
}

- Pratyay November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sortList(node **head1){

    //1-->2-->3-->4-->5-->0-->2
    node *current=*head1;
    while( current != NULL && current->next!=NULL && current->data < current->next->data ){
        current=current->next;
    }

    if (current == NULL){
        return;
    }

    node *head2=current;
    if (head2->next != NULL && head2->next->data<(*head1)->data)
    {
        node *temp=head2->next;
        current->next=head2->next->next;
        temp->next=*head1;
        *head1=temp;
        head2=current;
    }
    node *prev=head2;
    head2=head2->next;
    node *head=*head1;
    while(head2!=NULL){
        if(head2->data <= head->next->data){
            node *temp=head2;
            prev->next=head2->next;
            insert(head,temp);
            head=head->next;
            head2=prev->next;
        }
        else{
            head=head->next;
        }
    }
}

- Anonymous December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void MergeHalfSortedList(stIntList* pHead)
{
if(NULL == pHead)
return;

stIntList* pTemp = pHead;
stIntList* pHead2 = pHead;
stIntList* pList1Last = pHead;
while(pHead2 != NULL)
{
if(pHead2->pNList != NULL && pHead2->data > pHead2->pNList->data) //condition when second list head is found
{
pList1Last = pHead2;
pHead2 = pHead2->pNList;
break;
}

pList1Last = pHead2;
pHead2 = pHead2->pNList;
}

if(pHead2 == NULL)
{
std::cout<<"\nList is already Sorted\n";
return;
}

//Now Head 2 is found Merge them into single list
stIntList* pTemp2 = pTemp;
stIntList* pRoot = NULL;
stIntList* pCurr = NULL;
pList1Last->pNList = NULL;
while((pTemp2 != NULL) && (pHead2 != NULL))
{
if(pCurr == NULL)
{
if(pTemp2->data > pHead2->data)
{
pCurr = pHead2;
pHead2 = pHead2->pNList;
}
else
{
pCurr = pTemp2;
pTemp2 = pTemp2->pNList;
}
pRoot = pCurr;
continue;
}

if(pTemp2->data > pHead2->data)
{
pCurr->pNList = pHead2;
pCurr = pCurr->pNList;
pHead2 = pHead2->pNList;
}
else
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
continue;

}
if(pHead2)
{
while(pHead2)
{
pCurr->pNList = pHead2;
pCurr = pCurr->pNList;
pHead2 = pHead2->pNList;
}
}
else if(pTemp2)
{
while(pTemp2)
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
}

printIntList(pRoot);
}

- Anonymous March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void MergeHalfSortedList(stIntList* pHead)
{
if(NULL == pHead)
return;

stIntList* pTemp = pHead;
stIntList* pHead2 = pHead;
stIntList* pList1Last = pHead;
while(pHead2 != NULL)
{
if(pHead2->pNList != NULL && pHead2->data > pHead2->pNList->data) //condition when second list head is found
{
pList1Last = pHead2;
pHead2 = pHead2->pNList;
break;
}

pList1Last = pHead2;
pHead2 = pHead2->pNList;
}

if(pHead2 == NULL)
{
std::cout<<"\nList is already Sorted\n";
return;
}

//Now Head 2 is found Merge them into single list
stIntList* pTemp2 = pTemp;
stIntList* pRoot = NULL;
stIntList* pCurr = NULL;
pList1Last->pNList = NULL;
while((pTemp2 != NULL) && (pHead2 != NULL))
{
if(pCurr == NULL)
{
if(pTemp2->data > pHead2->data)
{
pCurr = pHead2;
pHead2 = pHead2->pNList;
}
else
{
pCurr = pTemp2;
pTemp2 = pTemp2->pNList;
}
pRoot = pCurr;
continue;
}

if(pTemp2->data > pHead2->data)
{
pCurr->pNList = pHead2;
pCurr = pCurr->pNList;
pHead2 = pHead2->pNList;
}
else
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
continue;

}
if(pHead2)
{
while(pHead2)
{
pCurr->pNList = pHead2;
pCurr = pCurr->pNList;
pHead2 = pHead2->pNList;
}
}
else if(pTemp2)
{
while(pTemp2)
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
}

printIntList(pRoot);
}

- rishikantku March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution tested for all cases. Basically compares and swap the elements of first part with the second part of the list. After swapping, the new element in the second part is then sorted so the second part remain sorted.
Whenever the two pointers/references meet, the list is completely sorted.

public void mergeAndSort(MyNode<Integer> current)
	{
		if(current == null)
		{
			return;
		}
		
		MyNode<Integer> temp = current;
		
		while(temp.next!=null)
		{
			if(temp.data > temp.next.data)
			{
				break;
			}
			temp = temp.next;
		}
		
		if(temp.next == null)
		{
			return;
		}
				
		MyNode<Integer> temp1 = temp.next;
		temp = current;
		
		while(temp !=null)
		{
			while(temp!=null && temp.data <= temp1.data && temp != temp1)
			{
				temp = temp.next;
			}
			
			if(temp == temp1)
			{
				// The list is sorted.
				return;
			}
			
			// swap:
			Integer val = temp.data;
			temp.data = temp1.data;
			temp1.data = val;
			
			MyNode<Integer> temp2 = temp1;
			
			while(temp2.next != null && temp2.data>temp2.next.data)
			{
				// swap temp1 and temp2:
				Integer val1 = temp2.data;
				temp2.data = temp2.next.data;
				temp2.next.data = val1;
				
				temp2 = temp2.next;
			}			
		}

}

- obaidsalikeen May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/** Convert 1-->2-->3-->4-->5-->1-->2-->null  into
	 * 	   1-->1-->2-->2-->3-->4-->5-->null	*/
	public static LinkedListNode<Integer> arrangeLinkedList(LinkedListNode<Integer> head){
		// Base conditions i.e. either list is empty or contains just one node
		if(head == null || head.getNext() == null){
			return head;
		}
		
		LinkedListNode<Integer> first_list = head;
		LinkedListNode<Integer> splitNode = head;
		LinkedListNode<Integer> sec_list = head.getNext();
		
		// Traverse to position/point each node in proper location
		while(splitNode != null && sec_list != null && splitNode.getValue() < sec_list.getValue()){
			splitNode = splitNode.getNext();
			sec_list = sec_list.getNext();
		}
		
		/* 	Another corner condition: Traversed complete list but didn't found any new secondary list 
			i.e existing list is already arranged */
		if(sec_list == null){
			return head;
		}
		
		/* if my sec_list contains smaller number then rearrange it 
		 * so that my first_list is always of smaller value */ 
		while(sec_list != null && first_list.getValue() > sec_list.getValue()){
			splitNode.setNext(sec_list.getNext());
			sec_list.setNext(first_list);
			head = sec_list;
			sec_list = splitNode.getNext();
		}
		
		// traverse till end of second_list is empty or first_list intersects with second list
		while(sec_list != null && first_list != sec_list){
			if(first_list.getNext().getValue() >= sec_list.getValue()){
				splitNode.setNext(sec_list.getNext());
				sec_list.setNext(first_list.getNext());
				first_list.setNext(sec_list);
				sec_list = splitNode.getNext();
			}else if(first_list.getNext().getValue() < sec_list.getValue()){
				first_list = first_list.getNext();
			}else{
				sec_list = sec_list.getNext();
			}
		}
		return head;	// return the head, since head may change based on the initial link list
	}

- Ketan Mehta September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/** Convert 1-->2-->3-->4-->5-->1-->2-->null  into
	 * 		  1-->1-->2-->2-->3-->4-->5-->null	*/
	public LinkedListNode<Integer> arrangeList(LinkedListNode<Integer> head){
		// Base conditions i.e. either list is empty or contains just one node
		if(head == null || head.getNext() == null){
			return head;
		}
		
		LinkedListNode<Integer> first_list = head;
		LinkedListNode<Integer> splitNode = head;
		LinkedListNode<Integer> sec_list = head.getNext();
		
		// Traverse to position/point each node in proper location
		while(splitNode != null && sec_list != null 
				&& splitNode.getValue() < sec_list.getValue()){
			splitNode = splitNode.getNext();
			sec_list = sec_list.getNext();
		}
		
		/* 	Another corner condition: Traversed complete list 
		 * 	but didn't found any new secondary list 
		 * 	i.e existing list is already arranged */
		if(sec_list == null){
			return head;
		}
		
		/* if my sec_list contains smaller number then rearrange it 
		 * so that my first_list is always of smaller value */ 
		while(sec_list != null 
				&& first_list.getValue() > sec_list.getValue()){
			splitNode.setNext(sec_list.getNext());
			sec_list.setNext(first_list);
			head = sec_list;
			sec_list = splitNode.getNext();
		}
		
		/* traverse till end of second_list is empty or 
			first_list intersects with second list */
		while(sec_list != null && first_list != sec_list){
			if(first_list.getNext().getValue() >= sec_list.getValue()){
				splitNode.setNext(sec_list.getNext());
				sec_list.setNext(first_list.getNext());
				first_list.setNext(sec_list);
				sec_list = splitNode.getNext();
			}else if(first_list.getNext().getValue() < sec_list.getValue()){
				first_list = first_list.getNext();
			}else{
				sec_list = sec_list.getNext();
			}
		}
		// return the head, since head may change based on the initial link list
		return head;
	}

- Ketan Mehta September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm new to data structures. Please correct me if im wrong anywhere.

public void combineSortedList(ListNode<T> node) throws EmptyListException{
		
		if(node == null){
			throw new EmptyListException();
		}
		
		ListNode<T> slow = node, fast = node, temp = null;
		
		//Iterate the fast pointer to the position before 2nd sorted list begins
		while((int)fast.getData() <= (int) fast.getNext().getData() ){ 	
			fast = fast.getNext();
		}
		
	//Now until the last element in the 2nd sorted list is replaced do a while loop
		while(fast.getNext() != null){
	// To check if current element and next element is smaller 
	// than the fast pointers next element
			if(slow.getData() >= fast.getNext().getData() ||  slow.getNext().getData() >= fast.getNext().getData()){
				temp = fast.getNext();
				fast.setNext(temp.getNext());
				temp.setNext(slow.getNext());
				slow.setNext(temp);
				slow = temp;
			}
			//Increment the slow pointer if the current value in 1st sorted 			//list is less than 2nd list value
			else if(slow.getData() < fast.getNext().getData()){
				slow = slow.getNext();
			}
		}
	}

- Ram December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LinkMerge {

List1 head;
boolean istrue=false;
public void insertlastlist(int data){

List1 new_node=new List1(data);
if(head==null){
head= new_node;

}else{

List1 current_node=head;
List1 previous_node=head;
while(current_node!=null){
previous_node=current_node;
current_node=current_node.next;
if(current_node==null){
previous_node.next=new_node;
}
}
}


}

public void printlist(List1 list){
while(list!=null){
System.out.println(list.data);
list=list.next;
}
}

public void sort(List1 head){
if(head==null){

System.out.println("Null list");

}else if(head.next!=null){

List1 current_node=head;
while(current_node.next!=null){
if(current_node.next.data>current_node.data){
current_node=current_node.next;
}else{
List1 sortnode=current_node.next;

current_node.next=sortnode.next;
List1 previous_node=head;
List1 next_node=head;
istrue=true;
while(istrue){
if(sortnode.data>next_node.data){
previous_node=next_node;
next_node=next_node.next;

}else{
previous_node.next=sortnode;
sortnode.next=next_node;
istrue=false;

}

}
}
}
}else{
System.out.println(head.data);
}

}

public static void main(String[] args) {

LinkMerge merge= new LinkMerge();
merge.insertlastlist(1);
merge.insertlastlist(5);
merge.insertlastlist(7);
merge.insertlastlist(8);
merge.insertlastlist(9);
merge.insertlastlist(2);
merge.insertlastlist(4);
merge.insertlastlist(6);

//merge.printlist(merge.head);
merge.sort(merge.head);

System.out.println("After sort");
merge.printlist(merge.head);
}

}

class List1{
int data;
List1 next;
List1(int data){
this.data=data;

}

}

- xyz July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function sortLinkList(){

    if(this.HeadNode === null) { return null}

    var head = this.HeadNode;
    var head2;
    
    /* find the head2 */
    while(head.next !== null && head.value < head.next.value){
        head = head.next;
    }
    
    head2 = head.next;
    head.next = null;
    head = this.HeadNode;
    
    this.HeadNode = mergeLinkList(head, head2);
    
}

/** Merge both Link List **/
function mergeLinkList(list1, list2){
  if(list1 === null && list2 === null){
        return null;
    }
  
    if(list1 === null && list2 !== null) { 
      return list2
    }
    if(list2 === null && list1 !== null) { 
      return list1
    }
    
    if(list1.value < list2.value){
        list1.next = mergeLinkList(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeLinkList(list2.next, list1);
        return list2;
    }
}

- Pravin Neema February 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stdio.h>
#include <stdlib.h>
struct node
{
int val;
struct node *next;
};
typedef struct node node;
node *push(node *head,int value)
{
node *temp=(node *)malloc(sizeof(node));
temp->val=value;
temp->next=head;
return temp;
}
void print(node *head)
{
while(head)
{
printf("%d ",head->val);
head=head->next;
}
printf("\n");
}
node *find_middle(node *head)
{
node *fast_ptr=head, *slow_ptr=head;
while(fast_ptr && fast_ptr->next)
{
fast_ptr=fast_ptr->next->next;
slow_ptr=slow_ptr->next;
}
return slow_ptr;
}
node *merge(node *a, node *b)
{
node *result;
if(!a && !b)
return NULL;
if(!b)
return a;
if(!a)
return b;
if(a->val<=b->val)
{
result=a;
result->next=merge(a->next,b);
}
else
{
result=b;
result->next=merge(a,b->next);
}
return result;
}
int main()
{
node *start=NULL,*start2,*result;
int value;
char c;
node *middle_node;
printf("Enter value for list\n");
do
{
scanf("%d",&value);
start=push(start,value);
printf("Do you want to continue ? (y/n)");
getchar();
c=getchar();
}while(c=='y' || c=='Y');
print(start);
middle_node=find_middle(start);
start2=middle_node->next;
middle_node->next=NULL;
result=merge(start,start2);
print(result);
return 0;
}

- munai September 28, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More