Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Not exactly sure what Matt meant by "merge" here. If he meant just joining the independent list pointers, then the logic does not work for all scenarios. Below is one example where it does not work:
3->6->9->1->2->4
@RK it will work even in your test case also
3->6->9->1->2->4
once you find a element which has value lower than previous which in your case is 1 then just merge the list starting at 1 and other starting at 3(ending at 9) as 2 separate sorted listed which can now be easily done in O(n) without any extra space.
//from jagat's post below
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
Here's the implementation of the algorithm given by Matt, which is just the Merge algorithm used by merge sort, with a preprocessing step before that to find the second sorted set.
void merge(node** list) {
if(list == null || *list == null)
return;
node* head = *list;
node* p1 = head, p2 = head->next;
while(p2 != null) {
if(p1.data > p2.data) {
p1->next = null;
break;
}
p1 = p1->next;
p2 = p2->next;
}
if(p2 == null)
return; //Already sorted
p1 = head
node* cur = (p1->data < p2->data ? p1 : p2);
*list = cur;
if(cur == p1) p1 = p1->next;
else p2 = p2->next
}
while(true) {
if(p1 == null) {
cur->next = p2;
break;
}
else if(p2 == null) {
cur->next = p2;
break;
}
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
}
}
Can you explain how you do the merge please, like
head->next=ptr1;
head=ptr1;
ptr1=ptr1->next;
what does this do?
I knew this question sounds bs, the in place merge is not found yet how to do:
{{stackoverflow.com/questions/2126219/how-to-merge-two-sorted-integer-array-in-place-using-on-time-and-o1-space-co}}
It is hard to merge sorted "arrays" in place. But it's quite easy to merge linked list.
Javascript:
function work(list){
var current = list.head, secondHalf;
while(current && current.next){
if(current.data > current.next.data){
secondHalf = current;
break;
}
current = current.next;
}
while(secondHalf.next){
var data = secondHalf.next.data;
current = list.head;
var prev = {data:null, next:current};
while(current && current.data < data){
prev = current;
current = current.next;
}
var newNode = secondHalf.next;
prev.next = newNode;
secondHalf.next = newNode.next;
newNode.next =current;
if(!prev.data)
list.head = prev.next;
}
}
#include <iostream>
using namespace std;
struct Node
{
int val;
Node* next;
};
void PrintList(Node* root)
{
cout<<"\n";
while(root)
{
cout<< root->val<< " ";
root = root->next;
}
}
void BuildList(Node** root)
{
int arr[] = {1,2,3,4,5,1,2};
Node* head = *root;
for(int i=0;i<7;i++)
{
Node* temp = new Node;
temp->val = arr[i];
temp->next = NULL;
if(*root)
{ head->next = temp;
head=head->next;
}
else
{
*root = head = temp;
}
}
}
void SortList(Node** root)
{
Node* second = *root;
while(second && second->next && second->val<second->next->val)
second = second->next;
Node* head2 = second->next;
second->next = NULL;
Node* head1 = *root;
Node* Current=NULL, *Current2 = NULL;
while( head1 && head2)
{
if(head1->val<head2->val)
{
if(Current)
{
Current->next = head1;
Current=Current->next;
}
else
Current2 =Current = head1;
head1 = head1->next;
}
else
{
if(Current)
{
Current->next = head2;
Current = Current->next;
}
else
Current2 =Current = head2;
head2 = head2->next;
}
}
while(head1)
{
Current->next = head1;
head1=head1->next;
Current = Current->next;
}
while(head2)
{
Current->next = head2;
head2=head2->next;
Current = Current->next;
}
Current->next = NULL;
*root = Current2;
}
int main()
{
Node* root = NULL;
BuildList(&root);
// PrintList(root);
SortList(&root);
PrintList(root);
return 0;
}
There is some bugs in my previous code . Here is tested code
Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;
Node * head=NULL;
Node * m=head;
while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
ptr2=ptr2->next;
}
while(ptr1!=NULL && ptr2!=NULL)
{
if(ptr1->data < ptr2->data)
{
if(head==NULL)
{
head=ptr1;
m=head;
ptr1=ptr1->next;
}
else
{
head->next=ptr1;
head=ptr1;
ptr1=ptr1->next;
}
}
else
{
if(head==NULL)
{
head=ptr2;
m=head;
ptr2=ptr2->next;
}
else
{
head->next=ptr2;
head=ptr2;
ptr2=ptr2->next;
}
}
}
if(ptr1==NULL)
{
head->next=ptr2;
}
if(ptr2==NULL)
{
head->next=ptr1;
}
return m;
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public class MergeList {
public static void main(String[] args) {
Node root = new Node(1);
root.next = new Node(2);
root.next.next = new Node(3);
root.next.next.next = new Node(4);
root.next.next.next.next = new Node(5);
root.next.next.next.next.next = new Node(1);
root.next.next.next.next.next.next = new Node(2);
//root.next.next.next.next.next.next.next = new Node(2);
Node temp = findMax(root);
//System.out.println(":::::" + temp.data);
Node temp1 = temp.next;
temp.next = null;
Node head = MergeLists(root, temp1);
while (head!=null) {
//System.out.println(" ");
System.out.print(head.data);
head = head.next;
}
}
static Node MergeLists(Node list1, Node list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
Node head;
if (list1.data <= list2.data) {
head = list1;
} else {
head = list2;
list2 = list1;
list1 = head;
}
while(list1.next != null && list2 != null) {
if (list1.next.data <= list2.data) {
list1 = list1.next;
} else {
Node tmp = list1.next;
list1.next = list2;
list2 = tmp;
}
}
if (list1.next == null) {
list1.next = list2;
}
return head;
}
public static Node merge(Node h1, Node h2) {
Node h3 = new Node(0);
Node current = h3;
boolean isH1Left = false;
boolean isH2Left = false;
while (h1 != null || h2 != null) {
if (h1.data <= h2.data) {
current.next = h1;
h1 = h1.next;
} else {
current.next = h2;
h2 = h2.next;
}
current = current.next;
if (h2 == null && h1 != null) {
isH1Left = true;
break;
}
if (h1 == null && h2 != null) {
isH2Left = true;
break;
}
}
if (isH1Left) {
while (h1 != null) {
current.next = h1;
current = current.next;
h1 = h1.next;
}
}
if (isH2Left) {
while (h2 != null) {
current.next = h2;
current = current.next;
h2 = h2.next;
}
}
h3 = h3.next;
return h3;
}
public static Node findMax(Node max) {
while (max.next != null) {
if (max.data > max.next.data)
break;
max = max.next;
}
return max;
}
public static Node findMin(Node min) {
Node max = findMax(min);
if(max.next.data < min.data)
return min;
else
return max.next;
}
}
I think I get a in-place sort algorithm, is anyone can help me check this methods, if it does not work well, please tell me, with my thanks.
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}LinkNode, *LinkList;
void create_list(int *a, int n, LinkList *L) {
int i;
LinkNode *temp, *p;
for(i = 0; i < n; i++) {
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = a[i];
p->next = NULL;
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
}
}
void resort_list(LinkList *L) {
LinkNode *p_second_start = NULL;
LinkNode *q = *L;
LinkNode *p = q->next;
LinkNode *temp = NULL;
int _is_fisrt = 0;
while(p != NULL && q->data <= p->data) {
q = p;
p = p->next;
}
if(p == NULL) {
return ;
}
p_second_start = p;
q->next = NULL; // turn a list to two list
p = *L;
*L = NULL;
q = p_second_start;
while(p != NULL && q != NULL) {
if(p->data <= q->data) {
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
p = p ->next;
} else {
if(*L == NULL) {
*L = q;
} else {
temp->next = q;
}
temp = q;
q = q->next;
}
}
if(p != NULL) {
temp->next = p;
}
if(q != NULL) {
temp->next = q;
}
}
void print_list(LinkList L) {
LinkNode *p = L;
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void main() {
LinkList L = NULL;
int a[] = {1, 5, 7, 9, 11, 2, 4, 6};
int n = sizeof(a) / sizeof(int);
create_list(a, n, &L);
print_list(L);
resort_list(&L);
print_list(L);
getchar();
}
#include<iostream>
using namespace std;
struct node
{
int k;
node *next;
};
node *HEAD = NULL;
node *l1=NULL,*l2=NULL,*l1_end=NULL;
node *create(int v)
{
node *n = new node;
n->k = v;
n->next = NULL;
return n;
}
void build(node *n)
{
if(HEAD == NULL)
HEAD = n;
else
{
node *m = HEAD;
while(m->next != NULL)
m = m->next;
m->next = n;
}
}
void show()
{
node *m = HEAD;
cout<<endl;
while(m!=NULL)
{
cout<<m->k<<"->";
m = m->next;
}
cout<<"NULL";
}
void sort()
{
node *m = HEAD;
if(l1->k <= l2->k)
{
HEAD = m = l1;
l1 = l1->next;
}
else
{
HEAD = m = l2;
l2 = l2->next;
}
while((l1 != l1_end) && (l2 != NULL))
{
if(l1->k <= l2->k)
{
m->next = l1;
m = m->next;
l1 = l1->next;
}
else
{
m->next = l2;
m = m->next;
l2 = l2->next;
}
}
while(l1 != l1_end)
{
m->next = l1;
m = m->next;
l1 = l1->next;
}
while(l2 != NULL)
{
m->next = l2;
m = m->next;
l2 = l2->next;
}
m->next = NULL;
}
void separate()
{
node *m = HEAD;
while(m!=NULL)
{
if((m->next != NULL) && (m->k > m->next->k))
{
l1 = HEAD;
l1_end = l2 = m->next;
sort();
return;
}
m = m->next;
}
cout<<"List is not compatible.";
}
int main()
{
int x;
char ch;
do
{
cout<<"Enter the key : ";
cin>>x;
build(create(x));
cout<<"Want to enter more (y/n) ? : ";
cin>>ch;
}while(ch == 'y');
show();
separate();
show();
return 0;
}
public void sortList(){
//first = points to the head,last=points to the beginning of second half
LinkedList first=head,last=head;
while(last.next.value>last.value){
last=last.next;
}
LinkedList temp=last;
last=last.next;
//iterate over the second half of the list
LinkedList count =last;
while(count.next!=null){
//if element of second half of the list lies between the first value and its next
//then create a new node and add it in between them
if(count.value<first.next.value){
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}else{
//increment first pointer till you get a value greater than the count pointer value
while(first.next.value<count.value)
first=first.next;
}
count=count.next;
}
//this part for the last node
if(count.next==null){
if(count.value<first.next.value){
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}else{
while(first.next.value<count.value)
first=first.next;
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}
}
temp.next=null;
}
public void sortList(){
//first = points to the head,last=points to the beginning of second half
LinkedList first=head,last=head;
while(last.next.value>last.value){
last=last.next;
}
LinkedList temp=last;
last=last.next;
//iterate over the second half of the list
LinkedList count =last;
while(count.next!=null){
//if element of second half of the list lies between the first value and its next
//then create a new node and add it in between them
if(count.value<first.next.value){
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}else{
//increment first pointer till you get a value greater than the count pointer value
while(first.next.value<count.value)
first=first.next;
}
count=count.next;
}
//this part for the last node
if(count.next==null){
if(count.value<first.next.value){
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}else{
while(first.next.value<count.value)
first=first.next;
LinkedList temp1 = new LinkedList(count.value);
temp1.next=first.next;
first.next=temp1;
}
}
temp.next=null;
}
Hello, could you check my implementation? To merge the lists what I do is:
1. Find the middle - where the second list starts and save this node
2. Compare the values of the start and the middle lists, if the value of the start is smaller than the value of the second list - > move the pointer of the first part to ne next element.
If the the other part is greater then:
1 step Create a new Node with the value of the element;
2 stepCreate a node - pointer to the next element of the second list;
3 step remove the node of the second list
4 step add the new node to the element before the current element of the first list
5 step move the current element of the second list to point to the next element - the node create in step 2
Here is the code in Java:
//2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
//Sample test case:
//Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
//Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11
public class MergeLinkedLists {
public static void main(String[] args) {
List list = new List();
list.addToEnd(1).addToEnd(9).addToEnd(13).addToEnd(15);
// the next sorted part of the list
list.addToEnd(5).addToEnd(6).addToEnd(14).addToEnd(15).addToEnd(20);
System.out.println(list);
list.mergeLists();
System.out.println(list);
}
public static class List {
Node head;
int count;
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node linkToStart = head;
while (linkToStart != null) {
sb.append(linkToStart.val + " - > ");
linkToStart = linkToStart.next;
}
return sb.toString();
}
public void mergeLists() {
Node linkToList1 = head;
Node linkToList2 = findTheStartOfTheSecondPart();
while (linkToList1.next != null && linkToList2.next != null) {
if (linkToList1.val <= linkToList2.val) {
linkToList1 = linkToList1.next;
} else {
// copy node - I am not sure this is the best
Node n = new Node(linkToList2.val, null);
Node next = linkToList2.next;
remove(linkToList2);
addBefore(linkToList1, n);
linkToList2 = next;
}
}
}
private Node findTheStartOfTheSecondPart() {
// find the starting point of the second sorted linked list
Node linkToList1 = head;
Node linkToList2 = null;
int tmpVal = -1;
if (linkToList1 != null)
tmpVal = linkToList1.val;
while (linkToList1 != null) {
linkToList1 = linkToList1.next;
if (linkToList1.val < tmpVal) {
linkToList2 = linkToList1;
break;
} else {
tmpVal = linkToList1.val;
}
}
return linkToList2;
}
public void add(int val) {
add(new Node(val, null));
}
public void add(Node node) {
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
count++;
}
public void swapWithNext(int val1) {
Node linkToHead = head;
while (linkToHead.next != null) {
if (linkToHead.val == val1) {
int tmp = linkToHead.val;
linkToHead.val = linkToHead.next.val;
linkToHead.next.val = tmp;
return;
}
linkToHead = linkToHead.next;
}
}
/**Add before by the node - compared by its value
* @param beforeNode
* @param node
*/
public void addBefore(Node beforeNode, Node node) {
addBefore(beforeNode.val, node.val);
}
/**
* Add before node - it adds after and then swap the values
* @param beforeNodeVal
* @param nodeVal
*/
public void addBefore(int beforeNodeVal, int nodeVal) {
addAfter(beforeNodeVal, nodeVal);
swapWithNext(beforeNodeVal);
}
public void addAfter(int afterNodeVal, int nodeVal) {
Node afterNode = new Node(afterNodeVal, null);
Node node = new Node(nodeVal, null);
addAfter(afterNode, node);
}
public void addAfter(Node afterNode, Node node) {
Node linkToHead = head;
while (linkToHead.next != null) {
if (linkToHead.val == afterNode.val) {
Node nextNode = linkToHead.next;
linkToHead.next = node;
node.next = nextNode;
return;
}
linkToHead = linkToHead.next;
}
linkToHead.next = node;
}
/**
* Add Element to the end of the linked list
*
* @param val
* the value of the element
*/
public List addToEnd(int val) {
return addToEnd(new Node(val, null));
}
/**
* Adds element to the end of the linked list
*
* @param node
*/
public List addToEnd(Node node) {
if (head == null)
head = node;
else {
Node linkToHead = head;
while (linkToHead.next != null) {
linkToHead = linkToHead.next;
}
linkToHead.next = node;
}
return this;
}
public Node getHead() {
return head;
}
/**
* Remove the head element of the linked list
*
* @return the Head node of the linked list
*/
public Node removeHead() {
if (head == null)
return null;
else {
Node pointerToHead = head;
head = head.next;
return pointerToHead;
}
}
/**
* Remove an element from the linked list - it searched the elements and
* removes after it finds one with the same value
*
* @param val
* the value of the element which will be removed
* @return true if the element has been removed
*/
public boolean remove(int val) {
return remove(new Node(val, null));
}
public boolean remove(Node node) {
if (head == null)
return false;
else {
Node pointerToHead = head;
while (pointerToHead.next != null) {
if (pointerToHead.val == node.val) {
pointerToHead.val = pointerToHead.next.val;
pointerToHead.next = pointerToHead.next.next;
return true;
}
pointerToHead = pointerToHead.next;
}
}
return false;
}
}
/**
* @author lyubo Node of Linked List
*/
public static class Node {
int val;
Node next;
/**
* Constructor of the Node class
*
* @param val
* @param next
*/
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
Node linkToNode = this;
StringBuilder sb = new StringBuilder();
while (linkToNode != null) {
sb.append(linkToNode.val + " -> ");
linkToNode = linkToNode.next;
}
return sb.toString();
}
}
}
I will be very happy if someone can check my merge method and idea. Thanks :)
Node merge2SortedHalfsOfLinkedLists(final Node head) {
Node p1 = head;
Node p2 = head.next;
while (p2 != null) {
if (p2.key < p1.key) {
break;
}
p1 = p1.next;
p2 = p2.next;
}
p1.next = null;
Node previous = null;
while (p1 != null) {
if (p2 != null) {
if (p2.key < p1.key) {
Node temp = p2.next;
if (p1 == head) {
p2.next = p1;
} else {
previous.next = p2;
p2 = p2.next;
}
p2 = temp;
}
} else {
break;
}
previous = p1;
p1 = p1.next;
}
return head;
}
Node merge2SortedHalfsOfLinkedLists(final Node head) {
Node p1 = head;
Node p2 = head.next;
while (p2 != null) {
if (p2.key < p1.key) {
break;
}
p1 = p1.next;
p2 = p2.next;
}
p1.next = null;
Node previous = null;
while (p1 != null) {
if (p2 != null) {
if (p2.key < p1.key) {
Node temp = p2.next;
if (p1 == head) {
p2.next = p1;
} else {
previous.next = p2;
p2 = p2.next;
}
p2 = temp;
}
} else {
break;
}
previous = p1;
p1 = p1.next;
}
return head;
}
working code with time complexity o(n);
#include <iostream>
using namespace std;
class list{
public:
int value;
list* next;
list* end;
list(int v){
value = v;
next = NULL;
end = this;
}
bool insert(int v){
if(end->next!=NULL){
list* t = new list(v);
t->next = this->next;
this->next = t;
return true;
}
list* nlist = new list(v);
end->next = nlist;
end = nlist;
return true;
}
void print(){
cout<<endl;
list* c = this;
while(c){
cout<<c->value<<" ";
c=c->next;
}
}
};
list* array2LL(int *a,int size){
if(size==0) return NULL;
list* start = new list(a[0]);
for(int i=1;i<size;i++){
start->insert(a[i]);
}
return start;
}
int main () {
int a[]={5,6,5,6,7,8,9,10};
list* start = array2LL(a,8);
start->print();
list *i,*j;
j=start;
while(j->next){
if(j->value > j->next->value){
break;
}
j=j->next;
}
list *p = new list(0);
list *pdmp;
pdmp = p;
i = new list(0);
i->next = start;
start = i;
p->next = j->next;
j->next = NULL;
list *cstart, *cend;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value >= p->next->value){
cstart = p->next;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value < p->next->value){
cend = p;
break;
}
p = p->next;
}
if(!p->next){
j = i->next;
i->next = cstart;
p->next = j;
start->next->print();
return 0;
}
pdmp->next = p->next;
p=pdmp;
j = i->next;
i->next = cstart;
cend->next = j;
}
i=i->next;
}//*/
if(!i->next){
i->next = p->next;
}
start->next->print();
return 0;
}
Here is the merge function in java......let mw know if there is a problem with it
static Node listmerge(Node l1,Node l2){
Node lista=l1;Node listb=l2;
int flag=0;
Node start=null;
if(flag==0)
{
if(l2.data>l1.data)
start=l1;
else
start=l2;
flag=1;
}
while(lista!=null && listb!=null){
if(lista.data<listb.data)
{
l1=lista;
while(l1.next!=null && l1.next.data<=listb.data)
{
l1=l1.next;
lista=lista.next;
}
if(l1.next!=null){
lista=l1.next;
l1.next=listb;}
else
lista=lista.next;
}
else
{
l2=listb;
while(l2.next!=null && l2.next.data<=lista.data)
{
l2=l2.next;
listb=listb.next;
}
if(l2.next!=null){
listb=l2.next;
l2.next=lista;}
else
listb=listb.next;
}
}
//adding the remainder of other list
if(l1.next==null && l2.next!=null)
l1.next=listb;
if(l2.next==null && l1.next!=null)
l2.next=lista;
return start;
}
public class Node {
private final int val;
private Node next;
Node(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return val + "->" + (getNext() == null ? "null" : getNext().val);
}
}
public class Sort {
public Node mergeSortedList(Node root) {
Node r = new Node(0);
r.setNext(root);
Node p1 = r;
Node p2 = findLastOfFirst(root);
while (p2.getNext() != null) {
if(p1.getNext().getVal() <= p2.getNext().getVal()) {
p1 = p1.getNext();
} else {
Node temp = p1.getNext();
Node temp2 = p2.getNext().getNext();
p1.setNext(p2.getNext());
p2.getNext().setNext(temp);
p2.setNext(temp2);
}
}
return r.getNext();
}
Node findLastOfFirst(Node root) {
while(root.getVal() < root.getNext().getVal()) {
root = root.getNext();
if(root == null) {
throw new IllegalArgumentException("Can't find the second list");
}
}
return root;
}
}
public class SortTest {
private Sort sort;
@Before
public void setUp() throws Exception {
sort = new Sort();
}
@Test
public void test1() {
Node list = createList(1, 2, 3, 4, 5, 1, 2);
assertListEquals(list, 1,2,3,4,5,1,2);
list = sort.mergeSortedList(list);
assertListEquals(list, 1,1,2,2,3,4,5);
}
@Test
public void test2() {
Node list = createList(1, 5, 7, 9, 11, 2, 4, 6);
list = sort.mergeSortedList(list);
assertListEquals(list, 1,2,4,5,6,7,9,11);
}
@Test
public void test3() {
Node list = createList(4, 5, 7, 9, 11, 1, 2, 3);
list = sort.mergeSortedList(list);
print(list);
assertListEquals(list, 1,2,3,4,5,7,9,11);
}
@Test
public void testFindSecond() throws Exception {
Node list = createList(5, 6, 7, 8, 9, 3, 4);
Node second = sort.findLastOfFirst(list);
assertEquals(9, second.getVal());
}
private static Node createList(int... values) {
Node root = null;
Node current = null;
for(int value : values) {
Node node = new Node(value);
if(current != null) {
current.setNext(node);
}
current = node;
if(root == null) {
root = current;
}
}
return root;
}
private void print(Node list) {
while(list != null) {
System.out.print(list.getVal());
System.out.print(" ");
list = list.getNext();
}
System.out.println();
}
private void assertListEquals(Node list, int... values) {
for (int i = 0, valuesLength = values.length; i < valuesLength; i++) {
int value = values[i];
if (list == null) {
fail();
}
assertEquals("Failed at ["+i+"] element: ", value, list.getVal());
list = list.getNext();
}
if(list != null) {
fail();
}
}
}
Again, with indents:
package merge1;
/**
* User: igor
* Date: 25.01.13
* Time: 2:07
*/
public class Node {
private final int val;
private Node next;
Node(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return val + "->" + (getNext() == null ? "null" : getNext().val);
}
}
public class Sort {
public Node mergeSortedList(Node root) {
Node r = new Node(0);
r.setNext(root);
Node p1 = r;
Node p2 = findLastOfFirst(root);
while (p2.getNext() != null) {
if (p1.getNext().getVal() <= p2.getNext().getVal()) {
p1 = p1.getNext();
} else {
Node temp = p1.getNext();
Node temp2 = p2.getNext().getNext();
p1.setNext(p2.getNext());
p2.getNext().setNext(temp);
p2.setNext(temp2);
}
}
return r.getNext();
}
Node findLastOfFirst(Node root) {
while (root.getVal() < root.getNext().getVal()) {
root = root.getNext();
if (root == null) {
throw new IllegalArgumentException("Can't find the second list");
}
}
return root;
}
}
public class SortTest {
private Sort sort;
@Before
public void setUp() throws Exception {
sort = new Sort();
}
@Test
public void test1() {
Node list = createList(1, 2, 3, 4, 5, 1, 2);
assertListEquals(list, 1, 2, 3, 4, 5, 1, 2);
list = sort.mergeSortedList(list);
assertListEquals(list, 1, 1, 2, 2, 3, 4, 5);
}
@Test
public void test2() {
Node list = createList(1, 5, 7, 9, 11, 2, 4, 6);
list = sort.mergeSortedList(list);
assertListEquals(list, 1, 2, 4, 5, 6, 7, 9, 11);
}
@Test
public void test3() {
Node list = createList(4, 5, 7, 9, 11, 1, 2, 3);
list = sort.mergeSortedList(list);
print(list);
assertListEquals(list, 1, 2, 3, 4, 5, 7, 9, 11);
}
@Test
public void testFindSecond() throws Exception {
Node list = createList(5, 6, 7, 8, 9, 3, 4);
Node second = sort.findLastOfFirst(list);
assertEquals(9, second.getVal());
}
private static Node createList(int... values) {
Node root = null;
Node current = null;
for (int value : values) {
Node node = new Node(value);
if (current != null) {
current.setNext(node);
}
current = node;
if (root == null) {
root = current;
}
}
return root;
}
private void print(Node list) {
while (list != null) {
System.out.print(list.getVal());
System.out.print(" ");
list = list.getNext();
}
System.out.println();
}
private void assertListEquals(Node list, int... values) {
for (int i = 0, valuesLength = values.length; i < valuesLength; i++) {
int value = values[i];
if (list == null) {
fail();
}
assertEquals("Failed at [" + i + "] element: ", value, list.getVal());
list = list.getNext();
}
if (list != null) {
fail();
}
}
}
How about this?
class CCID15145684{
public static void printLinkedList(LinkedList<Integer> ll){
for(int i=0;i < ll.size();i++){
System.out.print(ll.get(i) + ", ");
}
System.out.println();
}
public static void fillLinkedList(LinkedList<Integer> ll){
// List 1: 1->2->3->4->5->1->2;
// ll.add(1); ll.add(2); ll.add(3); ll.add(4); ll.add(5); ll.add(1); ll.add(2);
// List 2: 1->5->7->9->11->2->4->6;
ll.add(1); ll.add(5); ll.add(7); ll.add(9); ll.add(11); ll.add(2); ll.add(4); ll.add(6);
}
public static void sortTwoHalfsOfALinkedList(LinkedList<Integer> ll){
// List 1: 1->2->3->4->5->1->2;
int ip = -1;
for(int i=1; i< ll.size(); i++){
if(ll.get(i-1) > ll.get(i)){
ip = i;
break;
}
}
System.out.println("Inflexion point = " + ll.get(ip));
int s1 = 0; int e1 = ip;
int s2 = ip; int e2 = ll.size();
while( (s1 < e1) && (s2 < e2)){
if(ll.get(s1) > ll.get(s2)){
ll.add(s1, ll.remove(s2));
s2++;
}else{
s1++;
}
}
}
}
void sort(struct node **base)
{
struct node *temp,*m,*n,*r;
temp=*base;
m=*base;
while( temp->link != NULL && temp->link->data > temp->data)
temp=temp->link;
n=temp->link;
if(m->data > n->data)
{
r=n;
n=n->link;
temp->link=n;
r->link=m;
*base=r;
m=*base;
}
while(m != n && n != NULL)
{
if(m->link->data > n->data)
{
r=n;
n=n->link;
temp->link=n;
r->link=m->link;
m->link=r;
}
m=m->link;
}
}
#include <stdlib.h>
#include <stdio.h>
struct linklist
{
int value;
struct linklist *next;
};
typedef struct linklist node;
void createList(node *head);
void printlist (node *head);
node *link_list_sort( node *head);
void redefine( node *head);
static int count=0;
main()
{
int ind;
node *head,*temp,*newHead;
head= (node*) malloc( sizeof(node));
createList(head);
printf("Given link list before sorting\n");
printlist(head);
printf("\nGiven link list after sorting\n");
newHead=link_list_sort(head);
printlist(newHead);
scanf("%d",&ind);
}
node *link_list_sort( node *head) {
node *local,*sortedList;
node *next_ptr,*local_head,*newHead,*local_nexPtr,*store_head;
int i;
if(head->next->next ==NULL){ printf(" Array is sorted\n"); return(head);}
else if( head->next->next->next ==NULL )
{
if( head->value <= head->next->value) { printf("\nArray is sorted\n"); return(head);}
else {
sortedList = head->next;
local=sortedList->next;
sortedList->next= head;
head->next =local;
return(sortedList);
}
}
else {
/*............Look for starting of 2nd starting sorted list..........*/
next_ptr = head->next;
local_head=head;
while( local_head->value <= next_ptr->value){
next_ptr=next_ptr->next;
local_head= local_head->next;
}
local_nexPtr= next_ptr;
//printlist(next_ptr);
local_head=head;
if( local_head->value >= next_ptr->value)
{
newHead = next_ptr;
next_ptr= next_ptr->next;
}
else{
newHead = local_head;
local_head= local_head->next;
}
store_head= newHead;
// printlist(store_head);
while ( (local_head != local_nexPtr) && (next_ptr != NULL))
{
// printf("\n local_head=%d---%dlocal_nexPtr=%d---%d next_ptr=%d---%d i m inside iff loop\n",local_head,*local_head,local_nexPtr,*local_nexPtr,next_ptr,*next_ptr);
if( local_head->value >= next_ptr->value)
{
newHead->next = next_ptr;
next_ptr= next_ptr->next;
newHead=newHead->next;
}
else{
newHead->next = local_head;
local_head= local_head->next;
newHead=newHead->next;
}
}
// printf("\n local_head=%d local_nexPtr=%d i m outside while\n",local_head,local_nexPtr);
if(( local_head !=local_nexPtr) && (next_ptr == NULL)){
while ( local_head !=local_nexPtr){
//printf("\n local_head=%d---%dlocal_nexPtr=%d---%d next_ptr=%d--- i m inside iff loop\n",local_head,*local_head,local_nexPtr,*local_nexPtr,next_ptr);
newHead->next = local_head;
local_head= local_head->next;
newHead=newHead->next;
}
newHead->next=NULL;
}
if(( local_head ==local_nexPtr) && (next_ptr != NULL)){
while ( (next_ptr != NULL)){
// printf("\n local_head=%d---%dlocal_nexPtr=%d---%d next_ptr=%d---%d i m inside iff loop\n",local_head,*local_head,local_nexPtr,*local_nexPtr,next_ptr,*next_ptr);
newHead->next = next_ptr;
next_ptr= next_ptr->next;
newHead=newHead->next;
}
newHead->next=NULL;
}
return(store_head);
}
}
void redefine(node *head){
node *localhead;
int i;
localhead= head;
while ( localhead->next->next != NULL){
localhead=localhead->next;
}
localhead->next->next= NULL;
}
void createList(node *head){
int n;
node *prenode;
printf("enter the value ( typ 9999 to end the list)\n");
scanf("%d",&head->value);
if( head->value != 9999){
head->next= (node *)malloc ( sizeof(node));
createList(head->next);
}
else
head->next= NULL;
return;
}
void printlist (node *head){
int i;
while ( head-> next != NULL && head->value != 9999)
{
printf("%d\t",head->value);
head=head->next;
}
// printf(".....%d \t",head->value);
}
Just an implementation of Matt's algo
Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;
Node * head=NULL;
Node * m=head;
while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
}
while(ptr1->next!=NULL && ptr2->next!=NULL)
{
if(ptr1->data < ptr2->data)
{
if(head==NULL)
{
head=ptr1;
m=head;
ptr1=ptr1->next;
}
else
{
head->next=ptr1;
head=ptr1;
ptr1=ptr1->next;
}
}
else
{
if(head==NULL)
{
head=ptr2;
m=head;
ptr1=ptr2->next;
}
else
{
head->next=ptr2;
head=ptr2;
ptr2=ptr2->next;
}
}
}
if(ptr1->next==NULL)
{
ptr1->next=ptr2;
}
if(ptr2->next==NULL)
{
ptr2->next=ptr1;
}
return m;
}
hi Peng , can you please help me to know complexity .. i think it is O(m*n) where m = number of elements in the first list and n = number of elements in the 2nd list .. is that correct ?
@hint
No, it's just O(n) where n is the length of the linked list. The first loop finds the start of the second sorted set and the second loop performs the merge and touches each node just once. If you notice, the loops are not nested. They're O(n) independently and hence O(n) overall.
Edit: Peng's loop that is supposed to find the second sorted set is buggy. It doesn't shift the pointers to the next nodes after it has examined a pair of nodes.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package string;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
*
* @author IYER HOME
*/
public class listmerge {
public void createList(List<Integer> list,int length)
{
int prev=0;
List list1=new ArrayList();
List list2=new ArrayList();
for(int i=0;i<length;i++)
{
int next=list.get(i);
if(prev < next)
{
list1.add(next);
prev=next;
}
else
{
list2.add(next);
}
}
System.out.println("List1 values"+list1);
System.out.println("List2 values"+list2);
mergeList(list1,list2);
}
public void mergeList(List list1,List list2)
{
List sortedList=new ArrayList();
System.out.println(sortedList);
int i=0;
int j=0;
while(i<list1.size()&&j<list2.size())
{
if((Integer)list1.get(i)<(Integer)list2.get(j))
{
sortedList.add(list1.get(i));
i++;
}
else
{
sortedList.add(list2.get(j));
j++;
}
}
while(i<list1.size())
{
sortedList.add(list1.get(i));
i++;
}
while(j<list2.size())
{
sortedList.add(list1.get(j));
j++;
}
System.out.println(sortedList);
}
public static void main(String args[]) throws IOException
{
List<Integer> list=new ArrayList<Integer>();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String val=br.readLine();
int length=Integer.parseInt(val);
int value_list;
for(int i=0;i<length;i++)
{
value_list=Integer.parseInt((br.readLine()));
list.add(value_list);
}
System.out.println(list);
listmerge merge=new listmerge();
merge.createList(list,length);
}
}
Use two pointers. 1st pointer goes through list. Keep moving forward with 1st pointer as long as the next node is greater than the previously. As soon as the value hasn't increased, then you know you've found the front of the 2nd list.
- Matt January 13, 2013Then start 2nd pointer at head, and merge the two lists like they were separate. Just make sure not to overlap the pointers.
Note: If the 1st pointer never finds a decreasing element, then every element in 2nd list was greater than every element in 1st list, so the lists when naturally sorted themselves.
O(n) runtime.