基礎練習之連結清單

簡單介紹

連結清單，每個節點離散的分布在記憶體中，通過next指針将節點進行連接配接(雙向連結清單多一個指針pre)。由于存在額外的指針，記憶體空間會比正常存儲資料要多一些。

一般結構

單連結清單節點

struct Node{
    TYPE val;
    struct Node* next;
};
           

雙向連結清單節點

struct Node{
    TYPE val;
    struct Node* pre;
    struct Node* next;
};
           

一般操作

連結清單的建立

此處讨論的是不包含頭指針的連結清單

頭插法

每次新添加的節點都變為頭節點。

每次添加一個節點

typedef TYPE int;
Node * insert(Node*head,TYPE val){
    Node * p = new Node();
    p->val = val;
    p->next = head;
    return p;
}
           

一次添加所有

Node * create_head(){
    // 頭插法
    Node * p=NULL;
    Node * head = NULL;
    int val;
    cin >> val;
    while(val !=-1){
        p = new Node();
        p->val = val;
        p->next = head;
        head = p;
        cin >> val;
    }
    return head;
}
           

尾插法

每次進來的節點為連結清單的尾插入到最後。

每次添加一個節點

Node * insert_tail(Node*head,TYPE val){
    //尾插法，如果head == NULL 傳回 節點 否則傳回 NULL
    Node * p = new Node();
    p->val = val;
    p->next = NULL;
    if(head == NULL){
        return p;
    }
    while(head->next!=NULL){
        head = head->next;
    }
    head->next = p;
    return NULL;
}
           

一次添加所有

Node * create_tail(){
    // 尾插法
    Node * tail=NULL;
    Node * p = NULL;
    Node * head = NULL;
    int val;
    cin >> val;
    while(val !=-1){
        p = new Node();
        p->val = val;
        if(head == NULL){
            head = p;
        }else{
            tail->next = p;
        }
        tail = p;
        cin >> val;
    }
    tail->next = NULL;
    return head;
}
           

插入資料

插入到第n個節點之後,分3中情況

1 頭節點為空，直接傳回新的節點

2都節點不為空，但是沒有n個節點，直接插入到最後

3正常插入到第n個節點後面。

Node * insert_n(Node * head,TYPE val,int n){
    //插入到第n個元素之後，如果沒有n個，直接插入到最後
    //head 為NULL 傳回新head，否則傳回NULL
    Node *p = new Node();
    p->val = val;
    if(head == NULL){
        p->next = NULL;
        return p;
    }
    int count = 1;
    while(count<n && head->next){
        head = head->next;
        ++count;
    }
    if(n == count){
        p->next = head->next;
        head->next = p;
    }else{
        head->next = p;
        p->next = NULL;
    }
    return NULL;
}
           

删除資料

删除第n個節點的資料

1 頭節點為空，直接傳回空

2 删除的資料為頭節點，連結清單隻有一個節點，傳回空

3 删除的資料為頭節點，連結清單不隻一個節點，傳回之後的節點

4 正常删除第n個節點的資料（或沒有第n個節點），傳回頭節點

Node * delete_n(Node *head,int n){
    // 1 頭節點為空，直接傳回空
    // 2 删除的資料為頭節點，連結清單隻有一個節點，傳回空
    // 3 删除的資料為頭節點，連結清單不隻一個節點，傳回之後的節點
    // 4 正常删除第n個節點的資料（或沒有第n個節點），傳回頭節點
    // n 從1開始
    if(head == NULL || n<=0){
        return head;
    }
    int count = 1;
    Node *p = head;
    if(n == 1){
        head = p->next;
        delete p;
        return head;
    }
    while(count <n-1 && p->next){
        ++count;
        p = p->next;
    }
    if(count == n-1){
        Node * q = p->next;
        if(q!=NULL){
            p->next = q->next;
            delete q;
        }
    }
    return head;
}
           

查找

查找給定的val是否存在，存在傳回true,不存在傳回false

bool find(Node* head,TYPE val){
    while(head){
        if(head->val == val){
            return true;
        }else{
            head = head->next;
        }
    }
    return false;
}
           

一般考點 部分參考來源

連結清單反轉

初始連結清單，p為空指針，q指向頭節點

指針t指向q的下一個節點，将q的下一個節點指向p，即将q的紅色箭頭變為綠色箭頭。

p 變成q,q變成t，即圖中紅色指針變為綠色指針

循環執行2和3 直到 q == NULL為止，傳回p.

Node * reverse(Node* head){
    Node* p = 0;
    Node* q = head;
    Node* t = NULL;
    while(q!=NULL){
        t = q->next;
        q->next = p;
        p = q;
        q = t;
    }
    return p;
}
           

兩個連結清單找交叉節點(判斷是否相交)

對齊法

如圖，如果找到兩個連結清單的頭部對齊的起點，然後兩個連結清單一次移動并判斷一個，相等時，就為找到的交點，否則就不相交。

對兩個連結清單計數，長的連結清單有countA個節點,短的連結清單有countB個節點。先移動短的連結清單，移動(countA - countB)個位置，然後兩個連結清單一起移動并判斷是否相等。相等就是交叉點，移動到結尾都不相等則不相交。

時間複雜度 O(A+B)

空間複雜度 O(1)

不會破環原來的連結清單結構

環找入口點法

這種方法其實是轉化為找帶環的連結清單的入口點，将其中一條連結清單的首尾相連。具體解發見找"連結清單環所在位置"

哈希解法

将第一個連結清單的節點位址存到哈希表中，然後周遊第二個連結清單，找到第一個存在于哈希表中的節點就是交叉節點。

時間複雜度 O(A+B)

空間複雜度 O(A)

找連結清單環入口所在位置

如圖所示，假設黑色的A節點繞進到圈内，和紅色的A重合了。将紅色A作為起點，兩個指針，一個走一步，一個走兩步。第一次相交的位置會在起點。此時一個指針在紅A,一個指針在黑A,同時都走一步，兩個節點相等時找到環的入口節點B。

Node * has_ring(Node * head){
    //有環傳回環的入口，否則傳回NULL,不可以改變原連結清單
    if(head == NULL || head->next == NULL){
        return head;
    }
    Node* slow = head->next;
    Node* fast = head->next->next;
    while(fast&&fast->next!=NULL && fast!=slow){
        slow = slow->next;
        fast = fast->next;
        if(fast){
            fast = fast->next;
        }
    }
    if(fast == slow){
        fast = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    } 
    return NULL;

}
           

求倒數k個節點

先讓p指針從head移動k個節點，此時讓a指針指向head，p和a同時移動，p到達連結清單尾部時，a到達倒數第k個位置。

Node *countdown_k(Node* head,int k){
    //倒數k個節點
    if(k<1){
        return NULL;
    }
    int count = 0;
    Node *p = head;
    while(count<k && p!=NULL){
        p = p->next;
        ++count;
    }
    if(p){
        Node*a = head;
        while(p->next){
            p = p->next;
            a = a->next;
        }
        return a->next;
    }
    return NULL;
}
           

代碼整理

點選這裡