Leetcode: Sort a linked list using insertion sort

Problem:

Sort a linked list using insertion sort.

Hide Tags

 Linked List Sort

Show Similar Problems

---------------------------------------
---------------------------------------
1. create a dummy node to function as the head when sorting, otherwise, head will be moved when sorting.

2. insertion sort performs from bottom to top in the second loop. Refer to here for insertion sort. But in listed nodes, move from bottom to top is impossible. So, we need to scan from top to down in the second loop.

3. operations about how to insert a node into a list. The pointer p in the outer loop should be update or should be move a step forward in each loop. But note that this move is not needed when a insertion occurs. see codes for details.

///////////////////////////////////////////////////
// codes

class Solution {

public:

       ListNode* insertionSortList(ListNode* head) {

              //check input

              if (head == NULL || head->next == NULL) return head;

              //create dummy node

              ListNode *dum = new ListNode(-1);

              dum->next = head;

              ListNode *p = head, *pScan = dum, *tmp = head;

              //sort

              while (p->next != NULL){

                     pScan = dum;

                     while (p->next != NULL){

                           if (pScan->next->val > p->next->val){

                                  //insertion; when insertion, don't need update p

                                  tmp = pScan->next;

                                  pScan->next = p->next;

                                  p->next = pScan->next->next;

                                  pScan->next->next = tmp;

                                  break;

                           }

                           else if (pScan == p){

                                  //uppdate p

                                  p = p->next;

                                  break;

                           }

                           pScan = pScan->next;

                     }

              }

              head = dum->next;

              delete dum;

              return head;

       }

};