C++, no dummy head, pointer-to-pointer trick


  • 1
    O

    This pointer-to-pointer trick is really addictive once you know how to use it !

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode * res = NULL, **pp = &res; // pp always points to the pointer which points to the last node
            while (l1 || l2) {
                if (!l1 || (l2 && l2->val < l1->val)) {
                    *pp = l2;
                    l2 = l2->next;
                }
                else {
                    *pp = l1;
                    l1 = l1->next;
                }
                pp = &((*pp)->next);
            }
            return res;
        }
    };
    

  • 0
    H

    @oldfish I don't have to reputation to upvote you, but I just thought your solution was awesome. Will be using pointer to pointer more often now.


  • 0
    J

    Hi could you elaborate on how the pointer to pointer trick works?
    Thanks.

    Actually let me try and reason it out and let me know if I got it...

    The pointer of a pointer (pp) gets the address of the result.
    The updates are applied through pp (which take effect on the result).
    Then the pp gets a new address to the next link in the result chain.

    Actually seems simple enough... nice! Will try to memorize this one.


  • 0
    O

    @jbrennan3 There is actually an interesting story behind this trick

    https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers


Log in to reply
 

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