Interview Questions And Answers 
-
Implement the following function for sorting a linked list of integers in ascending order. The function takes a pointer to the head of the list, and returns a pointer to the head of the sorted list. Your function should use only a constant amount of memory. It’s prohibited to change the value of ListNode, instead ListNodes must be rearranged. struct ListNode{ int value() { return _value; } ListNode *pNext;private: int _value;}; ListNode* SortList(ListNode *pHead){ // Insert your implementation here}
I need this implementation code
1,178 Views |
(34 votes, avg: 2.97)
Loading ...
Answers »
Our Sponsors
Our Sponsors
In this case, bubble sort is an obvious way to do it.
Swapping two (adjacents in this case) elemnts in the linked list shoud not be difficult.
Comments: O(n*2) running time in the worst case.
** No extra memory required.
/* Based on insertion sort */
Node *sort(Node *head)
{
Node *i, *j, *previ;
if (!head) return NULL;
i = head->next;
previ = head;
while (i) {
if (i->val val) {
previ->next = i->next;
i->next = head;
head = i;
} else {
j = head;
while (j->next != i && j->next->val val) {
j = j->next;
}
if (j->next != i) {
previ->next = i->next;
i->next = j->next;
j->next = i;
} else {
previ = previ->next;
}
}
i = previ->next;
}
return head;
}
Leave an Answer/Comment