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;

       }

};

Leetcode: Reverse a singly linked list (8ms)

Reverse a singly linked list.

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

--------------------------------------------------

-------------------------------------------------

1. create a dummy node and connects to head

2. insert the following nodes after dummy node one by one

This way we don't need to go through the whole list in head to get the final node. The logic is simple and easy to follow:

////////////////////////////////////////////////////////////

class Solution {

public:

    ListNode* reverseList(ListNode* head) {

        //check input

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

        ListNode *dummy= new ListNode(-1), *pre, *later;

        dummy->next=head;

        pre=head->next;

        later=pre->next;

        while(1){

            //insertion

            pre->next=dummy->next;

            dummy->next=pre;

            //check loop //NOTE: should check before updating points

            if(later==NULL)break;            

            //update pointers

            pre=later;

            later=pre->next;

        }

        head->next=NULL;//clear the tail

        return dummy->next;

    }

};