iT邦幫忙

2023 iThome 鐵人賽
DAY 5
1
Software Development

30天冒險之旅: 資料結構與演算法筆記挑戰系列 第 5 篇

資料結構 — 雙向鏈結串列(Double Link List)

15th鐵人賽
1130 瀏覽

  • 分享至 

  • xImage
    •  

一直想找Double Link List的Leetcode練習但始終找不到QQ，只能在讓大家多練習Single Link List了，如果只想看Leetcode，就跳到文章後面吧/images/emoticon/emoticon70.gif

雙向鏈結串列

https://ithelp.ithome.com.tw/upload/images/20230920/20162567rhemVqO4fF.png

每個節點包含兩個指針，一個指向下一個節點，一個指向前一個節點。

  • 優點 :雙向鍊錶可以雙向遍歷，從任何一個節點出發都可以方便地訪問前後的節點。

  • 缺點 : 占較大的記憶體
    具體是如何實作的
    現在，我們將使用C++來實現這種資料結構，並介紹如何進行一些基本操作。

結構

這個資料結構包含了一個資料，以及兩個指標，一個指向前一個節點，另一個指向後一個節點。

struct DoubleLinkListNode{
    int val;
    DoubleLinkListNode *next;
    DoubleLinkListNode *prev;
    DoubleLinkListNode() : val(0), next(nullptr), prev(nullptr) {}
    DoubleLinkListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
    DoubleLinkListNode(int x, DoubleLinkListNode *next, DoubleLinkListNode *prev) : val(x), next(next), prev(prev) {}
};

新增節點

從頭新增節點

將新節點加入最前面，然後把頭的前指標指向它。

void DoubleLinkList::addNode_front(int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
}

從尾端新增節點

把新節點接在目前最後一個節點的後面，同時讓新節點的前指標指向目前最後一個節點。

void DoubleLinkList::addNode_back(int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    DoubleLinkListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }
    while(current->next != nullptr){
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

插入節點

插入一個新節點到指定位置（seatNumber），可以是最前面或其他位置。這裡我們會建立一個新節點，然後透過指標找到要插入位置的前一個節點，接著進行連接操作，讓新節點占據指定位置。

void DoubleLinkList::insertNode(int seatNumber, int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    DoubleLinkListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }
    if (seatNumber == 0){
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
        return;
    }

    for(int i=0; i<seatNumber-1; i++){
        current = current->next;
    }
    newNode->next = current->next;
    newNode->prev = current;
    current->next = newNode;  
    newNode->next->prev = newNode;
}

刪除節點

為了確保 head 的值也被考慮到，我們新增了一個節點，讓它的下一個節點指向 head。然後，如果下一個節點是要被刪除的節點，我們只需進行以下兩個操作：

  1. 讓目前節點的下一個節點指向被刪除節點的下一個節點。
  2. 同時，被刪除節點的下一個節點的上一個節點指向目前節點。
void DoubleLinkList:: removeNode(int val){
    if(head == nullptr){
        cout << "list is empty" << endl;
        return;
    }
    DoubleLinkListNode *node = new DoubleLinkListNode();
    node->next = head;
    DoubleLinkListNode *current = node;
    while(current->next != nullptr){
        if(current->next->val == val){
            current->next = current->next->next;
            current->next->prev = current;
            break;
        }
        current = current->next;
    }
    head = node->next;
    delete node;
}

反轉串列

與單向連結串列相似，重要的是確保前端和後端都能正確地連接。

void DoubleLinkList::Reverse(){
    DoubleLinkListNode *current = head;
    DoubleLinkListNode *prev = nullptr;
    DoubleLinkListNode *next = nullptr;
    while(current != nullptr){
        next = current->next;
        current->next = prev;
        current->prev = next;
        prev = current;
        current = next;
    }
    head = prev;
}

Double Link List 完整程式碼:

#include<iostream>
#include<string>
using namespace std;

struct DoubleLinkListNode{
    int val;
    DoubleLinkListNode *next;
    DoubleLinkListNode *prev;
    DoubleLinkListNode() : val(0), next(nullptr), prev(nullptr) {}
    DoubleLinkListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
    DoubleLinkListNode(int x, DoubleLinkListNode *next, DoubleLinkListNode *prev) : val(x), next(next), prev(prev) {}
};

class DoubleLinkList{
    private:
        DoubleLinkListNode *head;
    public:
        DoubleLinkList(){
            head = nullptr;
        }
        void addNode_front(int val);
        void addNode_back(int val);
        void insertNode(int seatNumber, int val);
        void removeNode(int val);
        void outputNode();
        void Reverse();
};
void DoubleLinkList::addNode_front(int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
}
// 將最後一個節點的next指向新節點
// 新節點的prev指向最後一個節點
void DoubleLinkList::addNode_back(int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    DoubleLinkListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }
    while(current->next != nullptr){
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

void DoubleLinkList:: removeNode(int val){
    if(head == nullptr){
        cout << "list is empty" << endl;
        return;
    }
    DoubleLinkListNode *node = new DoubleLinkListNode();
    node->next = head;
    DoubleLinkListNode *current = node;
    while(current->next != nullptr){
        if(current->next->val == val){
            current->next = current->next->next;
            current->next->prev = current;
            break;
        }
        current = current->next;
    }
    head = node->next;
    delete node;
}

void DoubleLinkList::insertNode(int seatNumber, int val){
    DoubleLinkListNode *newNode = new DoubleLinkListNode(val);
    DoubleLinkListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }
    if (seatNumber == 0){
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
        return;
    }

    for(int i=0; i<seatNumber-1; i++){
        current = current->next;
    }
    newNode->next = current->next;
    newNode->prev = current;
    current->next = newNode;  
    newNode->next->prev = newNode;
}

void DoubleLinkList::outputNode(){
    DoubleLinkListNode *current = head;
    while(current != nullptr){
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
}

void DoubleLinkList::Reverse(){
    DoubleLinkListNode *current = head;
    DoubleLinkListNode *prev = nullptr;
    DoubleLinkListNode *next = nullptr;
    while(current != nullptr){
        next = current->next;
        current->next = prev;
        current->prev = next;
        prev = current;
        current = next;
    }
    head = prev;
}

int main(){
    DoubleLinkList data;
    data.addNode_back(1);
    data.addNode_back(2);
    data.addNode_back(3);
    data.addNode_front(4);

    data.outputNode();

    data.removeNode(2);
    data.outputNode();

    data.insertNode(1, 5);
    data.outputNode();

    return 0;
}

Leetcode

Link List的題目好多，今天再來介紹兩題吧!

234. Palindrome Linked List

程度 : Easy 

題目解釋

給定一個single linked list，請判斷是否有迴文。

想法

**迴文（Palindrome）**是一個非常有趣的概念，它指的是無論是正著念或反著念，都會得到相同的結果。換句話說，這就是一個在兩個方向上都相同的字串或序列。
換句話說，迴文就像一個鏡子，它在反轉之後和原本一樣。簡單來說，迴文就是前後對稱的。

但是，當我們要判斷一個字串是否為迴文時，在單向的連結串列中可能會面臨一些挑戰。因為在單向連結串列中，我們只能順著一個方向移動，無法像迴文那樣同時從兩端向中間移動，逐一比對是否相同。
所以，要在單向連結串列中判斷是否為迴文，我們需要使用一些巧妙的方法。

法一

複製一份原本的連結串列，然後反轉其中一份。這麼做的原因是，直接在原本的連結串列上進行反轉操作可能會影響到原本的結構，所以我們需要保留一份原本的連結串列。接著，我們比對這兩份連結串列，看它們是否相同。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode *copy = copyList(head);
        ListNode *reverse = Reverse(copy);
        ListNode *current = head;
        while(current != nullptr && reverse!= nullptr){
            if(current->val != reverse->val ){
                return false;
            }
            else{
                current = current->next;
                reverse = reverse->next;                
            }
        }
        return true;
    }
    ListNode* Reverse(ListNode* head){
        if (head == nullptr)
            return nullptr;
        ListNode *current = head;
        ListNode *prev = nullptr;
        ListNode *next = nullptr;
        while(current != nullptr){
            next = current-> next;
            current->next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    ListNode* copyList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        ListNode *newHead = new ListNode(head->val);
        ListNode *current = newHead;
        ListNode *currentHead = head;
        while(currentHead->next != nullptr){
            current->next = new ListNode(currentHead->next->val);
            current = current->next;
            currentHead = currentHead->next;
        }
        return newHead;
    } 
};

法二

先找到連結串列的中間位置，然後將後半部分反轉。這樣，前半部分和反轉後的後半部分應該是相同的。這種方法省去了複製連結串列和完全反轉的時間，使我們更有效率地判斷是否為迴文。這個方法讓我們在連結串列中同步從兩端向中間移動，逐一比對節點的值是否相同。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode *slow = head;
        ListNode *fast  = head;
        // 使用快慢指針找到串列的中點
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 反轉後半部分的串列
        ListNode *secondHalf = Reverse(slow->next);
        // 從頭開始
        ListNode *firstHalf = head;
        while(firstHalf != nullptr && secondHalf!= nullptr){
            if(firstHalf->val != secondHalf->val ){
                return false;
            }
            else{
                firstHalf = firstHalf->next;
                secondHalf = secondHalf->next;                
            }
        }
        return true;
    }

    ListNode* Reverse(ListNode* head){
        if (head == nullptr)
            return nullptr;
        ListNode *current = head;
        ListNode *prev = nullptr;
        ListNode *next = nullptr;
        while(current != nullptr){
            next = current-> next;
            current->next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
        
};

不知道大家有沒有其他想法呢? 可以留言告訴我喔!

2807. Insert Greatest Common Divisors in Linked List

程度

Medium

題目

在原本的Linklist中，相鄰的節點間插入一個節點，其值為他們的最大公因數。

想法

  1. 最大公因數
  2. 插入節點
  3. 連上後，跳到下一個原始節點( 也就是要跳兩格)
    程式碼如下:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* ptr = head;
        while(ptr && ptr->next){
            ListNode* newnode = new ListNode( gcd(ptr->val,ptr->next->val),ptr->next);
            ptr->next = newnode;
            ptr = ptr->next->next;
        }
        return head;
    }
    int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }
};

終於開始敢踏入Leetcode Medium 題目了，不知道為什麼簡單的題目篇幅占比較大ㄟ

放下你認為最重要的事物，這不僅能夠減少壓力，讓你活得更開心，也能夠讓你看到更廣闊的世界。
/images/emoticon/emoticon29.gif


上一篇
資料結構 -- 單向鏈結串列(Single Link List)
下一篇
資料結構 — 環狀鏈結串列(Circular Link List)
系列文
30天冒險之旅: 資料結構與演算法筆記挑戰 共 30 篇
  1. 26
    演算法 —圖的走訪
  2. 27
    演算法 —連通元件(Connected Component)
  3. 28
    演算法 —最小生成樹（Minimum spanning tree)
  4. 29
    演算法 —路徑(Path)
  5. 30
    結語
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1058 組
團體組數
40 組
累計文章數
21740 篇
最後報名日
9/15
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙