My C++ solution by using pointer's pointer to do insertion.


  • 7
    B

    Short and easy way to manipulate the list.

    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            ListNode **node = &head;
            while ((*node)) {
                bool flag = false;
                for (ListNode **cmp=&head; *cmp!=*node; cmp=&(*cmp)->next) {
                    if ((*node)->val <= (*cmp)->val) {
                        //Do insertion
                        ListNode *tmp = *node;
                        *node = (*node)->next;
                        tmp->next = *cmp;
                        *cmp = tmp;
                        flag = true;
                        break;
                    }
                }
                //Node has been moved to the next already.
                if (flag) continue;
                node = &(*node)->next;
            }
            return head;
        }
    };

  • 0
    O

    Similar idea using only one pointer-to-pointer

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode * res = NULL, **pp = &res;
            while (head) {
                pp = &res;
                while (*pp && head->val >= (*pp)->val) {
                    pp = &((*pp)->next);
                }
                ListNode * nextHead = head->next;
                head->next = *pp;
                *pp = head;
                head = nextHead;
            }
            return res;
        }
    };
    

  • 0
    V

    @oldfish can you explain the logic behind the conditional in your second while loop?
    while (*pp && head->val >= (*pp)->val)


  • 1
    O

    pp always points to a pointer that points to a node (Yes this statement is indeed twisted...)

    For example, in the beginning, pp points to res. As you move pp along the list, pp will points to a next pointer of a certain node.

    When pp points a pointer that points to NULL, it means that it is the last node's next pointer. We insert the node here.

    If pp points to a pointer that points to a node which has smaller value than node to be inserted, it means that we haven't reached the place to insert the node. We move along the list. We insert the node to the location where the node larger than the node to be inserted.

    Example is 1->2->4, and we need to insert a node with value 3. Here pp will eventually points to the next pointer of 2, which points to the node 4, which is the first value that is larger than 3. We just need to change the value of *pp, which is the value of 2->next, to make it point to the node 3.

    Another example is 1->2, and we need to insert a node with value 3. Eventually pp will point to the next pointer of 2, which is NULL. In this case we still just need to modify *pp, which is 2->next.

    Hope this long and verbose explanation helps. Though I am not sure if it is a good idea to write such code in an interview. Too bug prone for me.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.