This is a very popular interview question, which most people go wrong.
The ideal solution to this problem is to keep the linked list sorted
as you build it. Another question on this website teaches you how to
insert elements into a linked list in the sorted order. This really
saves a lot of time which would have been required to sort it.
However, you need to Get That Job....
Method1 (Usual method)
The general idea is to decide upon a sorting algorithm
(say bubble sort). Then, one needs to come up with different scenarios
to swap two nodes in the linked list when they are not in the required
order. The different scenarios would be something like
1. When the nodes being compared are not adjacent and one of them
is the first node.
2. When the nodes being compared are not adjacent and none of them
is the first node
3. When the nodes being compared are adjacent and one of them
is the first node.
4. When the nodes being compared are adjacent and none of them
is the first node.
example bubble sort for a linked list goes like this (working C code!)...
#include
#include
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int *count, int value);
void print_list(char *listName, struct node *head);
mynode *bubbleSort(mynode *head, int count);
int main()
{
mynode *head;
int count = 0;
head = (struct node *)NULL;
add_node(&head, &count, 100);
add_node(&head, &count, 3);
add_node(&head, &count, 90);
add_node(&head, &count, 7);
add_node(&head, &count, 9);
print_list("myList(BEFORE)", head);
head = bubbleSort(head, count);
print_list("myList(AFTER) ", head);
getch();
return(0);
}
mynode *bubbleSort(mynode *head, int count)
{
int i, j;
mynode *p0, *p1, *p2, *p3;
for(i = 1; i < count; i++)
{
p0 = (struct node *)NULL;
p1 = head;
p2 = head->next;
p3 = p2->next;
for(j = 1; j <= (count - i); j++)
{
if(p1->value > p2->value)
{
// Adjust the pointers...
p1->next = p3;
p2->next = p1;
if(p0)p0->next=p2;
// Set the head pointer if it was changed...
if(head == p1)head=p2;
// Progress the pointers
p0 = p2;
p2 = p1->next;
p3 = p3->
next!=(struct node *)NULL?p3->next: (struct node *)NULL;
}
else
{
// Nothing to swap, just progress the pointers...
p0 = p1;
p1 = p2;
p2 = p3;
p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
}
}
}
return(head);
}
void add_node(struct node **head, int *count, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
*count = *count + 1;
}
void print_list(char *listName, struct node *head)
{
mynode *temp;
printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}
printf("NULL\n");
}
As you can see, the code becomes quite messy because of the pointer logic.
Thats why I have not elaborated too much on the code, nor on variations
such as sorting a doubly linked list. You have to do it yourself once to
understand it.
Method2 (Divide and Conquer using Merge Sort)
Here is some cool working C code...
#include
#include
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
void mergeSort(struct node** headRef);
struct node *merge2SortedLLs(struct node *head1, struct node *head2);
void splitLLInto2(struct node* source, struct node** frontRef,
struct node** backRef);
// The main function..
int main()
{
mynode *head;
head = (struct node *)NULL;
add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
print_list("myList", head);
mergeSort(&head);
print_list("myList", head);
getch();
return(0);
}
// This is a recursive mergeSort function...
void mergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
// Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL))
{
return;
}
// Split head into 'a' and 'b' sublists
splitLLInto2(head, &a, &b);
// Recursively sort the sublists
mergeSort(&a);
mergeSort(&b);
// Merge the two sorted lists together
*headRef = merge2SortedLLs(a, b);
}
// This is an iterative function that joins two already sorted
// Linked lists...
struct node *merge2SortedLLs(struct node *head1, struct node *head2)
{
struct node *a, *b, *c, *newHead, *temp;
a = head1;
b = head2;
c = (struct node *)NULL;
newHead = (struct node*)NULL;
if(a==NULL)return(b);
else if(b==NULL)return(a);
while(a!=NULL && b!=NULL)
{
if(a->value < b->value)
{
//printf("\na->value < b->value\n");
if(c==NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}
a = a->next;
}
else if(a->value > b->value)
{
//printf("\na->value > b->value\n");
if(c==NULL)
{
c = b;
}
else
{
c->next = b;
c = c->next;
}
b = b->next;
}
else
{
// Both are equal.
// Arbitraritly chose to add one of them and make
// sure you skip both!
if(c == NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}
a = a->next;
b = b->next;
}
// Make sure the new head is set...
if(newHead == NULL)
newHead = c;
}
if(a==NULL && b==NULL)
return(newHead);
if(a==NULL)
c->next = b;
else if(b==NULL)
c->next = a;
return(newHead);
}
// Uses the fast/slow pointer strategy
//
// This efficient code splits a linked list into two using
// the same technique as the one used to find the
// middle of a linked list!
void splitLLInto2(struct node* source, struct node** frontRef,
struct node** backRef)
{
struct node* fast;
struct node* slow;
if (source==NULL || source->next==NULL)
{
// length < 2 cases
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;
// Advance 'fast' two nodes, and advance 'slow' one node
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is before the midpoint in the list, so split it in two
// at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}
void print_list(char *listName, struct node *head)
{
mynode *temp;
printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}
printf("NULL\n");
}
The code to merge two already sorted sub-linked lists into a
sorted linked list could be either iterative or recursive.
You already saw the iterative version above. Here is a
recursive version of the same...
Recursive solution to merge two already sorted linked lists
into a single linked list
struct node* sortedMergeRecursive(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
result = a;
result->next = sortedMergeRecursive(a->next, b);
}
else
{
result = b;
result->next = sortedMergeRecursive(a, b->next);
}
return(result);
}
Also, see how the splitLLInto2() function uses the same technique used
to find the middle of a linked list to split a linked list into two
without having to keep a count of the number of nodes in the linked list.st!
Here is another solution (not that great, though) to split a linked list
into two.It used the count of the number of nodes to decide where to split
void splitLLInto2(struct node* source,struct node** frontRef,
struct node** backRef)
{
int len = Length(source); //Get the length of the original LL..
int i;
struct node* current = source;
if (len < 2)
{
*frontRef = source;
*backRef = NULL;
}
else
{
int hopCount = (len-1)/2;
for (i = 0; inext;
}
// Now cut at current
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}
Using recursive stack space proportional to the length of a list
is not recommended.However, the recursion in this case is ok ? it
uses stack space which is proportional to the log of the length of the list.
For a 1000 node list, the recursion will only go about 10 deep.
For a 2000 node list, it will go 11 deep. If you think about it,
you can see that doubling the size of the list only increases the depth by 1.
No comments:
Post a Comment