Double pointer is a great tool to simplify certain programming tasks.

Let’s look into a simple example: merge two sorted linked list by spicing together the nodes of the orignal lists without creating new nodes.

Below is the define of linked node:

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

The simplest way is use a pointer h to record the head of merged list, and use another pointer p to record the tail of merged results;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode* h = NULL, *p = NULL;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            if (!h) {
                h = p = l1;
            }
            else {
                p->next = l1;
                p = l1;
            }
            l1 = l1->next;
        }
        else {
            if (!h) {
                h = p = l2;
            }
            else {
                p->next = l2;
                p = l2;
            }
            l2 = l2->next;
        }
    }
    if (!h) h = l1 ? l1 : l2;
    else p->next = l1 ? l1 : l2;
    return h;
}

hmm, too many nested if else in the 28 line solution. How to elimate the detect of NULL of head? One trick is to use a dummy node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode dummy(-1), *p = &dummy;
    for (; l1 != nullptr && l2 != nullptr; p = p->next) {
        if (l1->val > l2->val) {
            p->next = l2;
            l2 = l2->next;
        }
        else { 
            p->next = l1;
            l1 = l1->next;
        }
    }
    p->next = l1 != nullptr ? l1 : l2;
    return dummy.next;
}

Here we got a 15 line solution, 13 lines are elimated. Here a dummy node elemated the check of NULL for head and prev pointer. But how can we elimate the construct of a new dummy load if the cost is heavy? Double pointer may help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode* h = NULL, **p = &h;
    for (;l1&&l2;p=&((*p)->next)) {
        if (l1->val <= l2->val) {
            *p = l1;
            l1 = l1->next;
        }
        else {
            *p = l2;
            l2 = l2->next;
        }
    }
    *p = l1 ? l1 : l2;
    return h;
}

Here’re some quizzes you can try with double pointer.