谈指神通

c/c++

浏览数:191

2019-4-1

都说指针是 C 语言的灵魂,其实这是由几个重量级的数据结构决定的,如最基础却又最重要的:链表二叉树两位元老,所有操作几乎都依赖指针。

可谓是:无指针者,无链表与二叉树也

想象一下,没有链表与二叉树,计算机世界将如何存在?

当然,数组的本质也是指针,但藏得较深,大家用脚标得过且过,倒也怡然自得。

若只论链表与二叉树,链表又更容易将指针指的出神入化,二叉树稍逊,一个 left, 一个 right 的二次元世界,弄不出什么花来。

所以想要把握指针的灵魂,练就一身弹”指”神通的俊功夫,还得多练练链表

下面,我就随意截取几道经典的链表问题,陪诸君练练手。(为简化问题,凸显实质,皆为单链表)

cppstruct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

链表的逆

 1->2->3->4->5
 ^
 root

想要逆序,最直接的想法,就是希望上图中的链表指向反过来。我们借用一个空指针 node 指向一个空节点:

 1->2->3->4->5 | ListNode* reverse(ListNode *root) {
 ^             |      ListNode *node = nullptr;    
 root          | }
               |
 null          |
 ^             |
 node          |

第一步,我们希望节点1从单链表中剥离,于是让其指向 node, 但我们不能因此而找不到链表索引,故需要一个额外的指针 next, 指向后续节点:

 2->3->4->5    | ListNode* reverse(ListNode *root) {
 ^             |      ListNode *node = nullptr;   
 root          |      ListNode *next = root->next;     // next refer to 2
               |      root->next = node;               // root point to node
 1->null       |      node = root;                     // node refer to root(1)
 ^             |      root = next;                     // root refer to next(2)
 node          | }

几个简单的指针转移,便将节点1反向的去指向了 node 节点。如法炮制的话,节点2, 节点3, 节点4, 节点5 都调转枪头,我们的目的便达到了。

cppListNode* reverse(ListNode *root) {
     ListNode *node = nullptr;
     while (root) {
          ListNode *next = root->next;
          root->next = node;
          node = root;
          root = next;
     }
     return node;
}

链表除重

1->1->2->2->3->4
^
head
cur

如果用一个指针 cur 来指向当前节点的话,出现重复的条件即为:cur->value == cur->next->value,如上图中,1 与 1 是重复的。我们只要想办法去掉重复的那个 1 即可。

1->1->2->2->3->4    |  if (cur->val == cur->next->val) {
^  ^  ^             |      ListNode *next = cur->next->next;
cur   next          |      delete cur->next;
|     ^             |      cur->next = next;
|_____|             |  }

这个思路简单,易懂,但这个问题却又是很多复杂问题的基础。还是需要注意的。

cppListNode *removeDuplicates(ListNode *head) {
    if (head == nullptr) return head;
    for (ListNode *cur=head; cur->next; )
        if (cur->val == cur->next->val) {
            ListNode *next = cur->next->next;
            delete cur->next;
            cur->next = next;
        } else { cur = cur->next; }
    return head;
}

链表合并

1->2->3
^
a
            ==>    1->4->2->5->3->6
4->5->6            ^
^                  new_list
b

这个问题本身非常简单,但想通过这个基本问题,引申出链表问题一个非常常见的技巧。即设立 dummy 节点,可以称为是傀儡节点,其作用在于让合成的新链表有一个着手点。这个节点的值可以随意,我们最终返回的,实际上是 dummy.next;

     a ------>         | while (a && b) {
0 -> 1   2   3         |     tail->next = a;
^    |  /|  /|         |     tail = a;
|    V / V / V         |     a = a->next;
|    4   5   6 -> null |     tail->next = b;
|    b ------>         |     tail = b;
dummy                  |     b = b->next;

要注意,每一步指针的捣腾都是按照顺序的,用笔纸画一画会比较清楚。

cppListNode *shuffleMerge(ListNode *a, ListNode *b) {
    ListNode dummy(0), *tail = &dummy;
    while (a && b) {
        tail->next = a;
        tail = a;
        a = a->next;
        tail->next = b;
        tail = b;
        b = b->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

移动节点

1->2->3            2->3
^                  ^
a                  a
            ==> 
1->2->3            1->1->2->3
^                  ^
b                  b

这个问题几乎不足为道,但这个操作,将有助于咱们更深入的对链表进行研究。封装这个操作,我们可以避免纠缠于非常基本的问题。(a 为 source(s), b 为 dest(d))

    s->s        |
    1  2->3     | void moveNode(ListNode **destRef, ListNode **sourceRef) {
  ->n           |     ListNode *newNode = *sourceRef;
 |  |           |     *sourceRef = newNode->next;
 |  V           |     newNode->next = *destRef;
 |  1->2->3     |     *destRef = newNode;
 ---d           | }

顺序合并

1->3->5      
         ==>  1->2->3->4->5->6
2->4->6

这也是非常基本的操作,结合上述的傀儡节点与 moveNode 两个技巧,应该可以很轻松的写出如下思路:

cppListNode *sortedMerge(ListNode *a, ListNode *b) {
    ListNode dummy(0), *tail = &dummy;
    for ( ;a && b; tail = tail->next) {
        if (a->val <= b->val) moveNode(&(tail->next), &a);
        else moveNode(&(tail->next), &b);
    }
    tail->next = a ? a : b;
    return dummy.next;
}

傀儡节点毕竟耗费了额外的空间,同样的思路,能否改进为不耗费额外空间呢?我们来思考另一个例子:

1->null
^
a
        ==>  1->2->3
2->3         ^  ^
^            a  b
b

这是一个简单到不能再简单的链表连接了,使用 a->next = b 即可完成。但若此刻指针 a 没有指向 1, 而是指向了 null, 想过怎么办没有?

1->null
    ^
    a
        ==> 1->2->3
2->3
^
b

我们展开想象,如果能把 b 指针"生生的挪到" a 的位置就好了。可不可以呢?再深入一点,指针 a 指向 null, 内存里应该是这样子:

 ____    ______    ______     |
|null|  |0x2342|  |0x6787|    | ListNode **aRef = &a; // 0x9899
|____|  |__a___|  |__&a__|    | *aRef = b; // 
0x2342   0x6787    0x9899     |
 ____    ______    ______     |  ______
| 2  |  |0x1221|  |0x3554|    | |0x1221|
|____|  |__b___|  |__&b__|    | |__&a__| // 当我们找指针 a 的地址时,实际却找到了 b.
0x1221   0x3554    0x0980     |  0x9899  // 所以现在的链表为:1->2->3.

理解了这个技巧后(在 C++ 中有一个更合适的名字:Reference, 引用),这个问题有一个更好的办法:

cppListNode *sortedMerge(ListNode *a, ListNode *b) {
    ListNode *ret = nullptr, **lastPtrRef = &ret;
    for (; a && b; lastPtrRef = &((*lastPtrRef)->next)) {
        if (a->val <= b->val) moveNode(lastPtrRef, &a);
        else moveNode(lastPtrRef, &b);
    }
    *lastPtrRef = a ? a : b;
    return ret;
}

思路完全一致,但不消耗额外空间。即无需傀儡,直接上位。

另,这个问题也可以用递归解决,权当额外思考题了(可能更加直观):

cppListNode *sortedMerge(ListNode *a, ListNode *b) {
    ListNode *ret = nullptr;
    if (a == nullptr) return b;
    else if (b == nullptr) return a;

    if (a->val <= b->val) { ret = a; ret->next = sortedMerge(a->next, b); }
    else { ret = b; ret->next = sortedMerge(a, b->next); }

    return ret;
}

顺序插入

4
^
newNode
               ==>  1->3->4->5->7->8
1->3->5->7->8
^
head

给一个有序链表 head, 一个新节点 newNode. 将新节点插入该链表中。

问题本身简单到不行,但我们仅仅是以此来复习一下上次所讲的三种策略。

  1. 直接插入法(教科书法)
  2. 傀儡节点
  3. 引用法(指针的指针)

首先最朴素的第一种方法,也是教科书上经常讲述的方案。在这个问题里,我们需要分别考虑两种情况:其一,newNode 的值比 head 还要小,那么它应该直接放到最前面(这个动作是连接而非插入);其二,newNode 的值比 head 要大,那么毫无疑问,需要遍历整个链表,找到 newNode 应该插入的位置,进行插入。

cpp1 2->3->4->5    |    if (*headRef == nullptr || (*headRef)->val >= newNode->val) {
^ ^             |        newNode->next = *headRef;
| head          |        *headRef = newNode;
newNode         |    } else {
----------------|        ListNode *curr = *headRef;
1->2        4->5|        while (curr->next != nullptr && curr->next->val < newNode->val)
   ^        ^   |            curr = curr->next;
   curr->3--|   |        newNode->next = curr->next;
         ^      |        curr->next = newNode;
         newNode|    }

简单又好理解。

然后我们来看看第二种,很常用的傀儡法。为了避免像上面分两种情况分别处理那么麻烦,不如自立山头,统一处理。

cppvoid sortedInsert(ListNode **headRef, ListNode *newNode) {
    ListNode dummy(0), *tail = &dummy;
    dummy.next = *headRef;

    while (tail->next != NULL && tail->next->val < newNode->val)
        tail = tail->next;
    newNode->next = tail->next;
    tail->next = newNode;
    *headRef = dummy.next;
}

可以看到,代码完全照搬上面的第二种情况。更加紧凑。

好了,最后我们来看看最精简的第三种方案,使用引用。细心的童鞋会发现,上面我们定位的一直是 curr->next 节点。这个 next 很罗嗦,但普通的插入,必须要知道前后节点,所以也是不得已为之。如果我们采用引用,则只需要知道后面的节点即可。

cpp1->3->5        | ListNode **currRef = headRef;
      ^        | while (*currRef != nullptr && (*currRef)->val < newNode->val)
  4-> curr     |     currRef = &((*currRef)->next);
  ^            | newNode->next = *currRef;
  newNode      | *currRef = newNode;

可以看到,我们将 newNode->next 指向 curr 节点后,直接将 newNode 节点生生挪到链表里去了。这是因为 currRef 处于链表中第 2 个(从 0 开始)位置,当 *currRef = newNode 之后,相当于将这个位置指向的地址换成了 newNode. 而 newNode 已经和后面的节点相连,所以很顺利的顺延了后续链表。

寥寥五行,非常精简。上述三种思路都应该掌握,而核心应该掌握最后一种方案。

链表排序

我们趁热打铁,上面讨论了 sortedInsert 方法的实现。那么我们倒过来,实现最基础的面试题,插入排序。

思路呢,非常简单,弄一个空链表:ListNode *newHead = nullptr;, 然后遍历整个链表,将每一个节点 sortedInsertnewHead 中。代码如下:

cppvoid insertSort(ListNode **headRef) {
    ListNode *newHead = nullptr;
    for (ListNode *curr = *headRef, *next; curr; curr = next) {
        next = curr->next;
        sortedInsert(&newHead, curr);
    }
    *headRef = newHead;
}

知道为什么面试官老说“连个插入排序都写不出,还能要?”的话了吧,因为就是这么简单。插入排序的关键在于插入。这也是我们上面大篇幅讲解链表三件套来实现顺序链表插入的原因。

这仅仅是最基础的一种排序手段,先留个思考题,还有那些常用的排序手段,如何实现呢?

未完待续