鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。如下圖：

下面處理的全部是單鏈表
單鏈表的基本結(jié)構(gòu)：

typedef struct node {
    char *data; 
    struct node *next; 
} node_t;

設(shè)定一個(gè)打印鏈表的函數(shù):

void list_display(node_t *head)
{
    for (; head; head = head->next)
        printf("%s ", head->data);
    printf("\n");
}

1.計(jì)算一個(gè)鏈表的長(zhǎng)度（復(fù)雜度O(n)）
算法：定義一個(gè)p指針指向頭結(jié)點(diǎn)，步長(zhǎng)為1，遍歷鏈表。

int list_len(node_t *head)
{
    int i; 
    for (i = 0; head; head = head->next, i++); 
    return i; 
}

2.反轉(zhuǎn)鏈表（復(fù)雜度O(n)）
算法：t遍歷鏈表, q記錄t的上一個(gè)結(jié)點(diǎn), p是一個(gè)臨時(shí)變量用來(lái)緩存t的值。

void reverse(node_t *head)
{
    node_t *p = 0, *q = 0, *t = 0; 
    for (t = head; t; p = t, t = t->next, p->next = q, q = p); 
}

3.查找倒數(shù)第k個(gè)元素（尾結(jié)點(diǎn)記為倒數(shù)第0個(gè)）（復(fù)雜度O(n)）
算法：2個(gè)指針p, q初始化指向頭結(jié)點(diǎn).p先跑到k結(jié)點(diǎn)處, 然后q再開(kāi)始跑, 當(dāng)p跑到最后跑到尾巴時(shí), q正好到達(dá)倒數(shù)第k個(gè)。

node_t *_kth(node_t *head, int k)
{
    int i = 0; 
    node_t *p = head, *q = head; 
    for (; p && i < k; p = p->next, i++); 
    if (i < k) return 0;
    for (; p->next; p = p->next, q = q->next); 
    return q; 
}

4.查找中間結(jié)點(diǎn)（復(fù)雜度O(n)）
算法：設(shè)兩個(gè)初始化指向頭結(jié)點(diǎn)的指針p, q.p每次前進(jìn)兩個(gè)結(jié)點(diǎn), q每次前進(jìn)一個(gè)結(jié)點(diǎn), 這樣當(dāng)p到達(dá)鏈表尾巴的時(shí)候, q到達(dá)了中間。

node_t *middle(node_t *head)
{
    node_t *p, *q; 
    for (p = q = head; p->next; p = p->next, q = q->next){
        p = p->next; 
        if (!(p->next)) break; 
    }
    return q; 
}

5.逆序打印鏈表（復(fù)雜度O(n)）
算法：使用遞歸（即讓系統(tǒng)使用棧）。

void r_display(node_t *t)
{
    if (t){
        r_display(t->next); 
        printf("%s", t->data);
    }
}

6.判斷一個(gè)鏈表是否有環(huán)（復(fù)雜度O(n)）
算法：設(shè)兩個(gè)指針p, q, 初始化指向頭.p以步長(zhǎng)2的速度向前跑, q的步長(zhǎng)是1.這樣, 如果鏈表不存在環(huán), p和q肯定不會(huì)相遇.如果存在環(huán), p和q一定會(huì)相遇。

int any_ring(node_t *head)
{
    node_t *p, *q; 
    for (p = q = head;p; p = p->next, q = q->next){
        p = p->next; 
        if (!p) break; 
        if (p == q) return 1; //yes
    }
    return 0; //fail find
}

7.找出鏈表中環(huán)的入口結(jié)點(diǎn)（復(fù)雜度O(n)）
算法：初始化三個(gè)指針p，q，r全部指向head，然后p以2的步長(zhǎng)行進(jìn)，q以1的步長(zhǎng)行進(jìn)。當(dāng)p和q相遇的時(shí)候，發(fā)出r指針以1的步長(zhǎng)行進(jìn)，當(dāng)p和r相遇的結(jié)點(diǎn)就是環(huán)的入口結(jié)點(diǎn)。

node_t *find_entry(node_t *head)
{
    node_t *p, *q, *r; 

    for (p = q = head; p; p = p->next, q = q->next){
        p = p->next; 
        if (!p) break; 
        if (p == q) break; 
    }

    if (!p) return 0; //no ring in list

    for (r = head, q = q->next; q != r; r = r->next, q = q->next); 

    return r; 
}

解析:

使用倆指針p和q, p掃描的步長(zhǎng)為1, q掃描的步長(zhǎng)為2.它們的相遇點(diǎn)為圖中meet處(在環(huán)上).
假設(shè)頭指針head到入口點(diǎn)entry之間的距離是K.則當(dāng)q入環(huán)的時(shí)候, p已經(jīng)領(lǐng)先了q為: d = K%n(n為環(huán)的周長(zhǎng)).
我們?cè)O(shè)meet處相對(duì)entry的距離(沿行進(jìn)方向)為x, 則有
(n-d)+x = 2x (p行進(jìn)的路程是q的兩倍)
解得x = n-d
那么當(dāng)p和q在meet處相遇的時(shí)候, 從head處再發(fā)出一個(gè)步長(zhǎng)為1的指針r, 可以知道, r和q會(huì)在entry處相遇!

8.判斷兩個(gè)鏈表是否相交（復(fù)雜度O(m+n)）
算法：兩個(gè)指針遍歷這兩個(gè)鏈表,如果他們的尾結(jié)點(diǎn)相同,則必定相交。

int is_intersect(node_t *a, node_t *b)
{
    if (!a || !b) return -1; //a or b is NULL
    for (; a->next; a = a->next); 
    for (; b->next; b = b->next); 
    return a == b?1:0; //return 1 for yes, 0 for no
}

** 9.找兩個(gè)相交的鏈表的交點(diǎn)**
算法：p，q分別遍歷鏈表a，b，假設(shè)q先到達(dá)NULL，此時(shí)從a的頭結(jié)點(diǎn)發(fā)出一個(gè)指針t，當(dāng)p到達(dá)NULL時(shí)，從b的頭結(jié)點(diǎn)發(fā)出s，當(dāng)s==t的時(shí)候即相交。

node_t *intersect_point(node_t *a, node_t *b)
{
    node_t *p, *q, *k, *t, *s; 
    for (p = a, q = b; p && q; p = p->next, q = q->next); 

    k = (p == 0)?q:p; //k record the pointer not NULL
    t = (p == 0)?b:a; //if p arrive at tail first, t = b ; else p = a
    s = (p == 0)?a:b; 
    for (; k; k = k->next, t = t->next); 
    for (; t != s; t = t->next, s = s->next); 
    return t; 
}

10.刪除結(jié)點(diǎn)d（不給頭結(jié)點(diǎn)）
算法：把下一個(gè)結(jié)點(diǎn)e的數(shù)據(jù)拷貝到d結(jié)點(diǎn)的數(shù)據(jù)區(qū)，然后刪除e。（缺陷：不能刪除尾結(jié)點(diǎn)）

node_t *delete(node_t *d) 
{
    node_t *e = d->next; 
    d->data = e->data; 
    d->next = e->next; 
}

11.兩個(gè)鏈表右對(duì)齊打印
算法：p和q兩個(gè)指針?lè)謩e遍歷鏈表a和b，假如q先到達(dá)NULL（即a比b長(zhǎng)），此時(shí)由a頭結(jié)點(diǎn)發(fā)出指針t，打印完整的鏈表a。同時(shí)p繼續(xù)移動(dòng)到NULL，并且打印空格。同時(shí)還從b頭結(jié)點(diǎn)發(fā)出指針s打印完整的鏈表b。

void foo(node_t *a, node_t *b)
{
    node_t *p, *q, *k, *t, *s; 
    for (p = a, q = b; p && q; p = p->next, q = q->next); 

    k = p?p:q; 
    t = p?a:b; 
    s = p?b:a; 

    for (; t; printf("%d ", t->data), t = t->next); 
    printf("\n");
    for (; k; printf("  "), k = k->next); 
    for (; s; printf("%d ", s->data), s = s->next); 
}

原文：https://github.com/hit9/oldblog/blob/gh-pages/blog-src/blog/C/posts/25.mkd