## 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.

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

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.

Enjoy coding!!!

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

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.

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

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

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

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){

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

}

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;
}``````

}

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

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

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;
}
}``````

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

Awesome!!

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

if (n1 == null)
{
n2->next=NULL;
return n2;
}
if (n2 == null)
{
n1->next = NULL;
return n1;
}

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

``````import java.util.Collections;
import java.util.List;

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

public static void main(String[] args) {
ll2.ll(l1, l2);

}

}``````

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

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

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

public static void main(String[] args) {
ll2.ll(l1, l2);

}

}

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

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

{
count++;
}

{
Node pervious = null;

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

{
{
}
}
}
}``````

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)

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;``````

}

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.

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.

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

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;
}``````

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

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

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?

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;
}``````

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

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;
}
{
{
}
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;
}
{
return ;
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;

}

int main()
{

}

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

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

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

{
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
}
cout<<"\nInput\n";
display(p);
mergelist(&p);
cout<<"\nOutput\n";
display(p);
}``````

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 display(struct node *);

int main() {
struct node *p = NULL;
display(p);
printf("\n");
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;
}
}

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;
}
}
}
}

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 display(struct node *);

int main() {
struct node *p = NULL;
display(p);
printf("\n");
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;
}
}

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;
}
}
}
}``````

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

{
lnode current =l1.root;
lnode wait;
{
}
lnode start=l1.root;
wait=current;
while (start!=null && current!=null)
{

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

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

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

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;
while(ptr->next != NULL) {
if(ptr->val > ptr->next->val) {
ptrBack = ptr->next;
ptr->next = NULL;
break;
}
ptr = ptr->next;
}
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;
}
}

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);
return 0;
}``````

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

``````struct node* sortList(struct node* 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)
else
prev->next = begin;
begin->next = state;
prev = begin;
begin = curr->next;
}
}
if (begin == NULL)
break;
}

}``````

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

``````struct node* sortList(struct node* 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)
else
prev->next = begin;
begin->next = state;
prev = begin;
begin = curr->next;
}
}
if (begin == NULL)
break;
}

}``````

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

``````void sortList(node **head1){

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

if (current == NULL){
return;
}

{
}
}
else{
}
}
}``````

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

{
return;

{
{
break;
}

}

{
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)
{
{
}
else
{
pCurr = pTemp2;
pTemp2 = pTemp2->pNList;
}
pRoot = pCurr;
continue;
}

{
pCurr = pCurr->pNList;
}
else
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
continue;

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

printIntList(pRoot);
}

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

{
return;

{
{
break;
}

}

{
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)
{
{
}
else
{
pCurr = pTemp2;
pTemp2 = pTemp2->pNList;
}
pRoot = pCurr;
continue;
}

{
pCurr = pCurr->pNList;
}
else
{
pCurr->pNList = pTemp2;
pCurr = pCurr->pNList;
pTemp2 = pTemp2->pNList;
}
continue;

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

printIntList(pRoot);
}

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;
}
}``````

}

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	*/
// Base conditions i.e. either list is empty or contains just one node
}

// 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){
}

/* 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);
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();
}
}
}``````

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	*/
// Base conditions i.e. either list is empty or contains just one node
}

// 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){
}

/* 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);
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();
}
}
}``````

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();
}
}
}``````

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

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

List1 new_node=new List1(data);

}else{

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;
}
}

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

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;
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{
}

}

public static void main(String[] args) {

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

System.out.println("After sort");
}

}

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

}

}

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

``````function sortLinkList(){

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

}

}

/** Merge both Link List **/
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){
return list1;
} else {
return list2;
}
}``````

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 *temp=(node *)malloc(sizeof(node));
temp->val=value;
return temp;
}
{
{
}
printf("\n");
}
{
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;
}

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.