Amazon Interview Question SDE1s
Team: TCS
Country: India
Interview Type: Written Test
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.
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!!!
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.
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;
}
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;
}
}
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;
}
}
some modification to your code:
if (n1 == null)
{
n2->next=NULL;
return n2;
}
if (n2 == null)
{
n1->next = NULL;
return n1;
}
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);
}
}
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);
}
}
// 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;
}
}
}
}
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;
}
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.
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;
}
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;
}
#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);
}
#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;
}
}
}
}
#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;
}
}
}
}
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;
}
}
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;
}
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;
}
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;
}
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;
}
}
}
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);
}
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);
}
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;
}
}
}
/** 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
}
/** 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;
}
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();
}
}
}
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;
}
}
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;
}
}
#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;
}
#include<stdio.h>
- nileshagarwal10 September 28, 2013#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);
}