|
Microsoft Interview Question for Software Engineers about Coding, Data Structures, Algorithms Linked List
Microsoft Interview Questions and Answers
(Continued from previous question...)
Microsoft Interview Question for Software Engineers about Coding, Data Structures, Algorithms Linked List
Question:
Sort a link list using merge sort.
maybe an answer:
// merge sort: returns a pointer to the head of a sorted list
list *merge_sort(list *head) {
if(head == 0)
return 0;
list *p = head, *pp = p, *prev = 0
if(p->next == 0)
return head; // already sorted
// find a split in the middle using two ptrs
while(pp != 0 && pp->next != 0) {
prev = p, p = p->next;
pp = pp->next->next;
}
prev->next = 0; // cut the list in the middle
list *h1 = merge_sort(p),
*h2 = merge_sort(head); // sort the two parts
head = h1, prev = 0;
// merge the list 'h2' into 'h1' inplace
while(h2 != 0) {
if(h1 != 0 && h2->val >= h1->val) {
prev = h1; // just iterater through 'h1' list
h1 = h1->next;
} else { // insert 'h2' before 'h1'
list *t = h2->next; // save the 'next' pointer
if(prev == 0) { // insert a new head
h2->next = head;
head = h2;
} else {
prev->next = h2;
h2->next = h1;
}
prev = h2; h2 = t;
}
}
return head;
}
(Continued on next question...)
Other Interview Questions
| 