二級指針, 詳見我以前的這篇博文, 看完了你應(yīng)該就有答案了http://czxyl.me/2017/05/14/In...

以防被墻, 在這里貼出原文.

title: Introduction to double pointers---part1
date: 2017-05-14 19:48:03
tags:
thumbnail: https://d3nmt5vlzunoa1.cloudf...
categories: [c/c++, tricky]

bgimage: https://d3nmt5vlzunoa1.cloudf...

[TOC]

這篇文章試圖從最簡單的例子入手展開指針的實(shí)用的技能. 考慮到這篇文章的某些讀者可能不是很熟悉c語言或者對指針仍然不是很熟悉, 所以我們先來看3個(gè)非常簡單的例子來熱下身, 不過為了增加點(diǎn)樂趣, 這里也會列出常見的一些錯(cuò)誤. 不過為了保證文章的流暢性, 關(guān)于指針的語法細(xì)節(jié)我不會多涉及. 雖然很多例子都可以改用reference而不是pointers, 但是這里用pointers能更好的講解, 有興趣的同學(xué)也可以自己嘗試用reference改寫例子, 畢竟多動手時(shí)提高的唯一方式啊... 本文采取的書寫方式主要是用問答式, 并且盡量將問題進(jìn)行分解, 也就是說每次提問的答案都很簡短, 但是問題會因此增多, 也會反復(fù)強(qiáng)調(diào)些要點(diǎn). 所以希望大家看到一個(gè)問題先做思考. 當(dāng)然如果大家發(fā)現(xiàn)我的答案和我的提問不匹配時(shí)希望能留言或者發(fā)郵件至czxyl@protonmail.com給我一個(gè)改正的機(jī)會, 謝謝.

warm up

case0: preface

int main()
{
    int *x = new int(1);
    int **x_address = &x;
}

Q0.1: 這里的x和x_address代表什么?
answer: x 代表1這個(gè)rvalue的地址, 也就是說它的值是就是一個(gè)整數(shù)的地址 或者說x這個(gè)地址上存儲著一個(gè)int 1, 如果我們對x進(jìn)行dereference, 得到的值就是1了 x_address代表著x這個(gè)地址的地址. 如果我們對x_address進(jìn)行dereference, 那么得到的值就是x, 也就是一個(gè)整數(shù)的地址了. 如果再進(jìn)一步dereference得到的就是1了. 所以本文就是圍繞著這么個(gè)最簡單的知識展開的.

case1: swap

swap: version A

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

swap: version B

void swap(int *a, int *b)
{
    int *temp = a;
    a = b;
    b = temp;
}

swap: version C

void swap(int **a, int **b)
{
    int ** temp = a;
    a = b;
    b = temp;
}

swap: version D

void swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}

Q1.1: 哪個(gè)version是對/錯(cuò)的?

answer: A是對的, B, C, D是錯(cuò)的.

Q1.2: A和B的區(qū)別是什么?

answer: 很明顯, A交換了a和b指向的address之上的value. 而B交換的是兩個(gè)address本身,
然而其上的value依然沒有變.

Q1.3: version C錯(cuò)在哪里(以后會省略前綴version)?

answer: 懂了B的錯(cuò)誤后, 很輕松的就能發(fā)現(xiàn)C里面交換的只是地址的地址. 所以最頂層的value依然是不變的. 這里提這個(gè)形式的例子主要是為了引出主題(double pointer)

case2: allocate

allocate: version A

void alloc1(int* p) {
   p = (int*)malloc(sizeof(int));
   *p = 10;
}
int main(){
   int *p = NULL;
   alloc1(p);
   printf("%d ",*p);
   free(p);
   return 0;
}

allocate: version B

void alloc2(int** p) {
   *p = (int*)malloc(sizeof(int));
   **p = 10;
}
int main(){
   int *p = NULL;
   alloc2(&p);
   printf("%d ",*p);
   free(p);
   return 0;
}

Q2.1: A與B的對錯(cuò)?

answer: A錯(cuò)B對

Q2.2: A會造成哪些問題?

answer: 1. 無法準(zhǔn)確打印出*p的值. 2. 會有內(nèi)存泄漏

Q2.3: swap::version D 與 allocate::version A有什么相同的錯(cuò)誤之處?

answer: 都妄圖通過傳value來改變value, 注意, 此處我定義的value是廣義上的, 就像allocate::version A傳入的是一個(gè)指針int *p, 同時(shí)接受的也是int *類型, 所以我在這里統(tǒng)一看做傳value. 與之相對的就是allocate::version B的傳參就是傳address了.

Q2.4: swap::version A 與 allocate::version B有什么相同的正確之處?

answer: 使用function來改變值時(shí)都傳入的是其地址.

Q2.5: 為什么無法準(zhǔn)確打印出*p的值?

answer: 結(jié)合Q2.3, 可以看出其實(shí)p是作為一個(gè)值傳入的. 自然alloc1()里面的p再怎么分配malloc也和main()中的p沒有關(guān)系了. 同時(shí), 由于alloc里面分配的內(nèi)存的所有權(quán)并沒有返回轉(zhuǎn)交到main()中, 所以會造成p = (int*)malloc(sizeof(int));出來的內(nèi)存就被拋棄了, 造成內(nèi)存泄漏

Q2.6: 如何確定真的出現(xiàn)了內(nèi)存泄漏了?

answer: 當(dāng)然, 這里比較直觀, 所以能肉眼看出來, 但是程序一旦復(fù)雜, 想檢測這種內(nèi)存泄漏的情況可就不一定能一眼看出來了. 所以我們需要一些工具, 比如vs下的_CrtDumpMemoryLeaks或者linux下的valgrind.

Q2.7: 詳細(xì)闡述下version B的正確性?

answer: 首先, 傳入的是一個(gè)int*的地址, 也可以說成pointer to pointer. 然后在這個(gè)地址的值(本質(zhì)也是一個(gè)地址)上開辟了空間*p = (int*)malloc(sizeof(int));. 因此相當(dāng)于在swap時(shí)需要往下探入一層(從value到address), 這里也是在地址上的基礎(chǔ)上再往下探入到地址的地址, 這樣地址能夠被在main()中的p保存. 因此allocate2()中對**p的修改也能在main()中反映.

Derive a conclusion from case1 and case2

我們想要通過函數(shù)修改任何一個(gè)值必須傳入它地址. 而不能僅僅傳入值, 即使它本身是一個(gè)地址, 而你想要修改的就是這個(gè)地址, 那么你需要做的就是傳入這個(gè)地址的地址. 不過寫到這里, 讀者可能還是不知道什么時(shí)候需要用到這種double pointers. 所以, 接下來我們通過各種例子來展示下此技巧的威力

Application for double pointers

Linkedlist

case 1: insert(tail)

這里的insert是在尾部插入結(jié)點(diǎn), 并且為了講解的效果, 這個(gè)例子不使用返回值, 統(tǒng)統(tǒng)使用void. 并且以下某些結(jié)論也是在僅使用void得出的. 如果返回head的話就沒討論的意義了......

insert: version A(trival && singal pointer)

void insert(node *head, node *inserted_node) //假設(shè)head是鏈表頭, inserted_node是帶插入尾部的已分配空間的結(jié)點(diǎn)
{
    node *current_node = head;
    if (current_node == NULL)
    {
        head = inserted_node;
    }
    else
    {
        while (current_node->next)
        {
            current_node = current_node->next;
        }
        current_node->next = inserted_node;
    }
}

insert: version B(non-trival && double pointers)

void insert(node **head, node *inserted_node)
{
    node **current_node = head;
    while (*current_node)
    {
        current_node = &(*current_node)->next;
    }
    *current_node = inserted_node;
}

insert: version C(trival && singal pointer)

void insert(node *head, node *inserted_node) 
{
    node *current_node = head;
    while (current_node)
    {
        current_node = current_node->next;
    }
    current_node = inserted_node;
}

Q1.1: version A省略掉if部分的判斷會怎么樣?

answer: 插入第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn))時(shí)會訪問到NULL->next, 非法內(nèi)存訪問.

Q1.2: version B為什么不需要這個(gè)version A的if條件?

answer: 想要回答這個(gè)問題, 只需要考慮version B在插入頭結(jié)點(diǎn)時(shí)的是如何處理的就行了. 與version A不同, version B是用*current_node做循環(huán)條件的, 而不是(*current_node)->next. 這樣做的好處是避免了NULL->next這樣的錯(cuò)誤步驟出現(xiàn).

Q1.3: version A可以寫成while (current_node)來避免使用if條件, 也就是version C這樣的嗎?

answer: 我們來看下完整的代碼, 希望讀者能上機(jī)運(yùn)行下

#include "stdafx.h"
class node
{
public:
    node *next;
    int elem;
    node(int e) : next{NULL}, elem{e} {}

};

void insert(node *head, node *inserted_node)
{
    node *current_node = head;
    while (current_node)
    {
        current_node = current_node->next;
    }
    current_node = inserted_node;
}

int main()
{
    node *head = NULL;
    node *inserted_node = new node(1);
    insert(head, inserted_node);
    inserted_node = new node(2);
    insert(head, inserted_node);
    return 0;
}

首先我們必須要搞清楚我們傳參的目的是什么, 以上面這份代碼為例, 我們的第一個(gè)insert其實(shí)是需要修改head的value, 但是, 我們我們傳入的其實(shí)也是head的value, 回想下文章開始的case1, case2, 毫無疑問, 這樣做的話, main()中的head依然是NULL, 得不到更新. 并且一直到return 0, head保持著NULL不變. 自然而然我們會想到把node *head = NULL替換為node head(you_choose_integer). 這樣做的話其實(shí)是和其它version邏輯稍有區(qū)別的, 即這里的頭結(jié)點(diǎn)是在main()里直接給出, 而不是insert中插入一個(gè)頭結(jié)點(diǎn). 當(dāng)然, 后面的邏輯依然是一致的. 下面給出完整代碼后我們繼續(xù)分析問題(依然沒有析構(gòu)僅供這里參考下)

#include "stdafx.h"
class node
{
public:
    node *next;
    int elem;
    node(int e) : next{NULL}, elem{e} {}

};

void insert(node *head, node *inserted_node) //假設(shè)head是鏈表頭, inserted_node是帶插入尾部的已分配空間的結(jié)點(diǎn)
{
    node *current_node = head;
    if (current_node == NULL)
    {
        head = inserted_node;
    }
    else
    {
        while (current_node->next)
        {
            current_node = current_node->next;
        }
        current_node->next = inserted_node;
    }
}
int main()
{
    node head(0);
    node *inserted_node = new node(1);
     insert(&head, inserted_node);
    inserted_node = new node(2);
    insert(&head, inserted_node);
    return 0;
}

好, 邏輯上終于修改完善了, 并且正確性大家上機(jī)測下很容易 我們以上面這份代碼來看Q1.3本身. 首先我們將代碼改為問題描述的樣子

#include "stdafx.h"
class node
{
public:
    node *next;
    int elem;
    node(int e) : next{NULL}, elem{e} {}

};

void insert(node *head, node *inserted_node) //假設(shè)head是鏈表頭, inserted_node是帶插入尾部的已分配空間的結(jié)點(diǎn)
{
    node *current_node = head;
    while (current_node->next)
    {
        current_node = current_node->next;
    }
    current_node->next = inserted_node;
}
int main()
{
    node head(0);
    node *inserted_node = new node(1);
     insert(&head, inserted_node);
    inserted_node = new node(2);
    insert(&head, inserted_node); 
    return 0;
}

首先看參數(shù)傳遞, 的確傳的是要修改的值的地址, 然后, 因?yàn)閙ain()中初始時(shí)有一個(gè)非NULL的頭結(jié)點(diǎn), 所以 while (current_node->next)不會出錯(cuò). 下面的問題我會進(jìn)一步講解這種寫法可能出錯(cuò)的地方. 但是這個(gè)其實(shí)是特例, 畢竟很少有這種把head一開始就定義的情況...不過下面的一些例子還是會讓大家看到有些情況double pointer能夠?qū)懗霰?code>singal pointer更簡練的代碼的.

Q1.4: 將Q1.3的answer里面while (current_node->next)改為while (current_node)會怎么樣?

answer: 這樣最后跳出時(shí)我們得到current_node是
NULL, 看上去是合理的, 給那個(gè)NULL賦值inserted_node就行了. 但是又有一個(gè)新問題, 給這個(gè)NULL賦值后我們能確保prev->next = inserted_node嗎? 這里其實(shí)是很反直覺的, 答案是不能, 首先我們要知道了next實(shí)際上都指向?qū)嶋H的內(nèi)存地址, 而當(dāng)current_node = NULL(循環(huán)終止條件)時(shí), 我們再給它進(jìn)行復(fù)制, prev結(jié)點(diǎn)的next依然是NULL, 因?yàn)樵谶@里current_node只是一個(gè)獨(dú)立的指針, 與鏈表結(jié)構(gòu)已經(jīng)無關(guān)了. 如果我們一定要這么做, 必須維護(hù)著一個(gè)實(shí)際存在的prev結(jié)點(diǎn).

Q1.5: 將Q1.3里面的最后一份代碼的第一步node head(0)改為node *head = new node(0); 會怎么樣?

answer:
其實(shí)這個(gè)問題的依舊隱藏著一個(gè)前提條件, 就是這樣修改依舊會實(shí)現(xiàn)在main()中定義好了一個(gè)頭結(jié)點(diǎn), 這樣的話即使形參實(shí)參都是node*類型, 也就是說沒有傳地址的情況, 依舊是正確的. 因?yàn)樗恍枰淖僪ead或者inserted_node, 只需要改變next就行了. 但是一旦寫成node *head = NULL, 就會犯NULL->next這樣的read access violation錯(cuò)誤了.

Q1.6：有沒有辦法將version A改為可以設(shè)置頭結(jié)點(diǎn)在insert建立?

answer: 沒有, 我們討論兩者情況,

1. node *head = NULL;
2. node head{0};

法1的問題是想修改head(題目要求)但是傳入的是node *head, 自然不能成功
法2的問題是這樣必須在main()中建立了一個(gè)value是0的頭結(jié)點(diǎn)了, 所以已經(jīng)與題意不符了.

Q1.7: 驗(yàn)證version B的正確性?

answer: 我們首先再回顧下(別怪我啰嗦, 我認(rèn)為這是最重要的), 傳入的是要修改的head的地址(別被形參和實(shí)參名一樣所迷惑, 他們代表的是兩個(gè)不同的東西, 形參是實(shí)參的地址). 我們先看對頭結(jié)點(diǎn)的處理: 將NULL的地址傳入, 并且修改為了inserted_node. 然后看非head結(jié)點(diǎn)的建立, 此時(shí)就需要用到while了. 我們分析下這個(gè)while的含義, 循環(huán)條件是對current_node進(jìn)行dereference, 判斷是不是NULL. 循環(huán)執(zhí)行語句是每次講current_node這個(gè)地址的地址下移(next). 邏輯還是很清楚的.

Q1.8: 本例中double pointers的優(yōu)勢在哪里?

answer: 可以任性的在main()中設(shè)置head, 比如node *head = NULL, 也可以node head(0), 也可以node *head = new node(0). 其他version就有著這樣那樣的限制.

case2: remove

這里remove是指移除滿足一定條件的結(jié)點(diǎn), 不限重復(fù). 在下面的例子中就是移除num是奇數(shù)的結(jié)點(diǎn). 沒有處理析構(gòu), 僅寫了兩份簡單代碼以便講解. 如果有不了解lambda的可以看version A, C, 不了解函數(shù)指針的可以看version B, D. 不過并不是c style的就是純粹的c了, 比如初始化列表什么的還是用的c++. 還有一點(diǎn)就是這里的single pointer不返回void了. 畢竟上面關(guān)于void的情況依舊討論了很多了, 沒必要繼續(xù)了. 雖燃insert的例子講了那么多關(guān)于值與地址, 但是僅僅為了更好的使讀者理解double pointers, 實(shí)際上在不使用void的情況下我們完全可以返回一個(gè)head來維護(hù)head, 即使傳入的是其value, 只要head = remove_if(...)來接受返回值就行了. 所以再接下來的講解中我們不過多關(guān)注value和address, 而是關(guān)注于代碼邏輯.

remove: version A(right && c style(not completely) && double pointers)

#include "stdafx.h"
#include <iostream>
typedef struct node
{
    struct node * next;
    int num;
    node(int x) : next{ NULL }, num{ x } {}
} node;

typedef bool(*remove_fn)(node const * v);

void remove_if(node ** head, remove_fn rm)
{
    for (node** curr = head; *curr; )
    {
        node * entry = *curr;
        if (rm(entry))
        {
            *curr = entry->next;
            delete entry;
        }
        else
            curr = &entry->next;
    }
}
bool find_odd(node const * x)
{
    if (x->num % 2 == 0)
    {
        return false;
    }
    return true;
}
int main()
{
    node *head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    remove_fn rm = find_odd;
    remove_if(&head, rm);
    return 0;
}

remove: version B(right && c++ style && double pointers)

#include "stdafx.h"
#include <iostream>
struct node
{
    struct node * next;
    int num;
    node(int x) : next{ NULL }, num{ x } {}
};

template<typename remove_fn>
void remove_if(node ** head, remove_fn rm)
{
    for (node** curr = head; *curr != NULL; )
    {
        node * entry = *curr;
        if (rm(entry))
        {
            *curr = entry->next;
            delete entry;
        }
        else
            curr = &entry->next;
    }
}

int main()
{
    node *head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    remove_if(&head, [&](node* temp) {return temp->num % 2 != 0; });
    return 0;
}

remove: version C(right && c style && single pointer)

#include "stdafx.h"
#include <iostream>
typedef struct node
{
    struct node * next;
    int num;
    node(int x) : next{ NULL }, num{ x } {}
} node;

typedef bool(*remove_fn)(node const * v);

node * remove_if(node * head, remove_fn rm)
{
    for (node * prev = NULL, *curr = head; curr != NULL; )
    {
        node * const next = curr->next;
        if (rm(curr))
        {
            if (prev)
                prev->next = next;
            else
                head = next;
            delete curr;
        }
        else
            prev = curr;
        curr = next;
    }
    return head;
}
bool find_odd(node const * x)
{
    if (x->num % 2 == 0)
    {
        return false;
    }
    return true;
}
int main()
{
    node *head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    remove_fn rm = find_odd;
    head = remove_if(head, rm);
    return 0;
}

remove: version D(right && c++ style && single pointer)

#include "stdafx.h"
#include <iostream>
struct node
{
    struct node * next;
    int num;
    node(int x) : next{ NULL }, num{ x } {}
};

template<typename remove_fn>
node * remove_if(node * head, remove_fn rm)
{
    for (node * prev = NULL, *curr = head; curr != NULL; )
    {
        node * const next = curr->next;
        if (rm(curr))
        {
            if (prev)
                prev->next = next;
            else
                head = next;
            delete curr;
        }
        else
            prev = curr;
        curr = next;
    }
    return head;
}

int main()
{
    node *head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head = remove_if(head, [&](node *temp) {return temp->num % 2 != 0; });
    return 0;
}

remove: version E(wrong && c++ style && single pointer)

#include "stdafx.h"
#include <iostream>
struct node
{
    struct node * next;
    int num;
    node(int x) : next{ NULL }, num{ x } {}
};

template<typename remove_fn>
node * remove_if(node * head, remove_fn rm)
{
    for (node* curr = head; curr; )
    {
        node * entry = curr;
        if (rm(entry))
        {
            curr = entry->next;
            delete entry;
        }
        else
            curr = entry->next;
    }
    return head;
}

int main()
{
    node *head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head = remove_if(head, [&](node *temp) {return temp->num % 2 != 0; });
    return 0;
}

Q2.1: version E有哪些錯(cuò)誤?

answer:

1. 沒有維護(hù)好head
2. 沒有維護(hù)好prev和next的羈絆(

Q2.2: version E該如何改正?

answer: refer to version C/D: 如果prev是NULL, 那么就該維護(hù)head了(head = next). 使用prev->next = next, prev = curr來維護(hù)羈絆. next還有一個(gè)作用就是在delete curr前保存著下一個(gè)結(jié)點(diǎn), 如果貪心省略掉這個(gè)next 你還是需要一個(gè)temp來保存的, 反而變丑了. 這也是寫代碼時(shí)容易忽略的一點(diǎn).

Q2.2: 分析這里兩個(gè)right version的邏輯差別?

answer: single pointer version都需要維護(hù)prev和next結(jié)點(diǎn), 而double pointers僅需要維護(hù)一個(gè)entry結(jié)點(diǎn)(除curr, 并且本質(zhì)上entry起著prev的作用). single pointer需要多一個(gè)判斷head的操作

Q2.3: double pointers version不需要判斷head(prev == NULL)?

answer: 這個(gè)問題依然要回到之前反復(fù)強(qiáng)調(diào)的value-address了, 傳入的head在這里是可以被修改的, 所以能在if里面直接維護(hù).

Q2.4: double pointers version是如何處理非head結(jié)點(diǎn)的?

answer: 這個(gè)問題也需要回到value-address來回答. 其實(shí)無論是head還是non-head, 處理方式都是一樣的----改變這個(gè)結(jié)點(diǎn)的地址為->next. 這樣是不會破壞與prev的羈絆的. 即使是NULL都無妨(ctrl/command f 任性, 參考這里).

case3: Insertion Sort for Singly Linked List

單鏈表的排序里面我覺得插排是最容易實(shí)現(xiàn)的, 所以在這里我使用它來講解 single pointer VS double pointers.

sort: version A(single pointer)

ListNode* linkedListSort(ListNode *head) {
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode *new_head = new struct ListNode(head->val); // 新鏈表的頭結(jié)點(diǎn)
    struct ListNode *current_node = head->next; // 遍歷舊鏈表
    struct ListNode *tail_node = new_head; // 新鏈表的最后一個(gè)結(jié)點(diǎn)
    while (current_node != NULL)
    {
        struct ListNode *temp_node = new_head; // 在新鏈表上進(jìn)行查找
        if (current_node->val < tail_node->val) // 需要進(jìn)行中間插入的情況, 為了維護(hù)tail_node, 這里不能是小于等于
        {
            if (new_head->val >= current_node->val) //比頭結(jié)點(diǎn)還小的情況
            {
                struct ListNode *new_new_head = new struct ListNode(current_node->val); // 新的頭結(jié)點(diǎn)
                new_new_head->next = new_head;
                new_head = new_new_head;
            }
            else if (new_head->next->val >= current_node->val) // 比頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)小但比頭結(jié)點(diǎn)大
            {
                struct ListNode *after_new_head = new struct ListNode(current_node->val);
                after_new_head->next = new_head->next;
                new_head->next = after_new_head;
            }
            else // 比頭結(jié)點(diǎn)和第二個(gè)結(jié)點(diǎn)都大的情況
            {
                while (temp_node->next->val <= current_node->val)
                {
                    temp_node = temp_node->next;
                }
                struct ListNode *middle_insert_node = new struct ListNode(current_node->val);
                middle_insert_node->next = temp_node->next;
                temp_node->next = middle_insert_node;
            }
        }
        else //直接放尾部的情況
        {
            struct ListNode *new_tail_node = new struct ListNode(current_node->val);
            tail_node->next = new_tail_node;
            tail_node = new_tail_node;
        }
        current_node = current_node->next;
    }
    return new_head;
}

Q3.1: 將上面那份代碼改寫為double pointers?

我的這個(gè)鏈表插排的寫法看起來的確很長, 但是勝在邏輯比較清楚, 可讀性很強(qiáng), 邊界條件也都處理的比較完善. 所以這也是我少有的用沒有智能提示的editor里寫一遍就能通過編譯的代碼, 如果讀者抱著學(xué)習(xí)的態(tài)度來看這篇文章但是上面那些例子都沒有自己動手寫, 那么希望能親自動手寫下這個(gè)問題, 為了方便大家盡快理解思路以免浪費(fèi)時(shí)間, 我在關(guān)鍵位置都寫了詳細(xì)的注釋.

answer:

ListNode* linkedListSort(ListNode *head) {
  // 很清楚的可以看到是O(n)復(fù)雜度
  if(head == NULL || head->next == NULL)
  {
      return head;
  }
  struct ListNode * new_head = NULL;
  while (head != NULL)
  {
      struct ListNode *   copy_of_head  = head;
      struct ListNode ** pointer_to_new_head = &new_head;
      head = head->next;
      while (!(*pointer_to_new_head == NULL || copy_of_head->val < (*pointer_to_new_head)->val ))
      {
          pointer_to_new_head = &(*pointer_to_new_head)->next;
      }
      copy_of_head->next = *pointer_to_new_head;
      *pointer_to_new_head = copy_of_head;
  }
  return new_head;
}

In Summary

可能很多人認(rèn)為指針是一個(gè)糟糕的特性, 也有很多人認(rèn)為掌握指針的各種技巧在C++11 里各種封裝好的smart pointer前只是班門弄斧. 但是我想說, 世界上不存在神這種玩意, 所以永遠(yuǎn)不要把一個(gè)人當(dāng)做神, 即使他/她再強(qiáng), 說的話也不應(yīng)該全盤被信任, 所以你必須做出自己的判斷, 這判斷不是為了判斷而判斷, 而是必須盡快的切換到學(xué)習(xí)知識而不是犯傻逼腦殘的所謂選擇困難癥的狀態(tài), 否則只會在一票大神面前永遠(yuǎn)迷失方向, 今天某大v說學(xué)這個(gè)是沒有意義的, 明天另一個(gè)大v說學(xué)那個(gè)是有意義的. 如果你信任所有人, 就會陷入什么都想學(xué), 卻什么都沒心思學(xué)的困境, 解決問題的唯一途徑就是憑著自己的興趣走下去, 何必管邊上的人所說的話?

等這些天手邊的事忙完后我在再寫一些 double pointers的其它應(yīng)用, 比如鏈表的其他操作, 樹的各種......