Post date: Sep 28, 2013 7:9:14 AM
Problem
/*
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
C/C++/Java/C#
struct node
{
int val;
node *next;
}
node* sortList(node* list1) {
}
Java
class Node
{
int val;
Node next;
}
Node sortList(Node list1) {
}
*/
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Sort integer linked list -- Amazon
Created Date : 28-09-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
typedef struct node
{
int val;
node *next;
} Node;
Node* CreateNode(int data)
{
Node* n = new Node;
n->val = data;
n->next = NULL;
return n;
}
Node* CreateList(int* arr, int len)
{
Node* h = CreateNode(arr[0]);
Node* prev = h;
for(int i = 1; i < len; i ++){
prev->next = CreateNode(arr[i]);
prev = prev->next;
}
return h;
}
void DisplayList(Node* h)
{
cout << "The list is " << endl;
while(h != NULL){
cout << setw(4) << h->val << " ";
h = h->next;
}
cout << endl;
}
Node* MergeList(Node* h1, Node* h2)
{
if(h1 == NULL) return h2;
if(h2 == NULL) return h1;
if(h2->val < h1->val) swap(h1, h2);
while(h1->next != NULL && h2 != NULL){
if(h1->next->val <= h2->val){
h1 = h1->next;
}
else{
Node* t1 = h1->next;
Node* t2 = h2->next;
h1->next = h2;
h2->next = t1;
h2 = t2;
}
}
return h1;
}
Node* FindSecondHalf(Node* h)
{
while(h->next != NULL){
if(h->val > h->next->val){
Node *sec = h->next;
h->next = NULL;
return sec;
}
h = h->next;
}
return NULL;
}
Node* ReSort(Node* h)
{
Node* h2 = FindSecondHalf(h);
DisplayList(h2);
cout << endl;
return MergeList(h, h2);
}
void DoTest(int* arr, int len)
{
Node* h = CreateList(arr, len);
cout << "before sorting" << endl;
DisplayList(h);
ReSort(h);
cout << "after sorting" << endl;
DisplayList(h);
cout << " ---------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr1[] = {1, 2, 3, 4, 5, 1, 2};
DoTest(arr1, sizeof(arr1)/sizeof(arr1[0]));
int arr2[] = {1, 5, 7, 9, 11, 2, 4, 6};
DoTest(arr2, sizeof(arr2)/sizeof(arr2[0]));
int arr3[] = {2, 4, 6, 1, 5, 7, 9, 11};
DoTest(arr3, sizeof(arr3)/sizeof(arr3[0]));
int arr4[] = {1, 2, 4, 5, 6, 7, 9, 11};
DoTest(arr4, sizeof(arr4)/sizeof(arr4[0]));
return 0;
}
Output
before sorting
The list is
1 2 3 4 5 1 2
The list is
1 2
after sorting
The list is
1 1 2 2 3 4 5
---------------------
before sorting
The list is
1 5 7 9 11 2 4 6
The list is
2 4 6
after sorting
The list is
1 2 4 5 6 7 9 11
---------------------
before sorting
The list is
2 4 6 1 5 7 9 11
The list is
1 5 7 9 11
after sorting
The list is
2 4 5 6 7 9 11
---------------------
before sorting
The list is
1 2 4 5 6 7 9 11
The list is
after sorting
The list is
1 2 4 5 6 7 9 11
---------------------
Press any key to continue . . .