今天，透過兩題Leetcode來做介紹吧

什麼是單向鏈結串列(Single Link List)

單向鏈結串列是一種資料結構，其中每個節點包含一個數據元素和一個指向下一個節點的指針。這種資料結構有其獨特的優點和缺點。

• 優點： 單向鏈結串列相對於其他資料結構來說佔用的內存較小。
• 缺點： 只能從頭節點開始遍歷，訪問後面的節點需要線性時間。

具體是如何實作的

現在，我們將使用C++來實現這種資料結構，並介紹如何進行一些基本操作。

結構

首先，我們需要定義一個節點的結構，包含一個整數值以及指向下一個節點的指針。

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) {}
 };

新增節點

在單向鏈結串列中，新增節點是一個基本操作，我們可以將它進一步細分為兩個部分：從頭新增和從尾端新增。

從頭新增節點

首先，我們創建一個新的節點，然後將新節點的下一個指向原始的頭節點，最後將頭節點指向新節點。

void Solution::addNode_front(int val){
    ListNode *newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

從尾端新增節點

我們創建一個新的節點，然後遍歷所有節點，直到找到尾節點，然後將尾節點的下一個指向新節點。

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

插入節點

在單向鏈結串列中，插入節點是一個常見的操作，用於在指定位置插入新節點。操作過程如下：

1. 首先，創建一個新的節點，然後使用一個指標遍歷鍊錶，直到找到要插入位置的前一個節點。
2. 一旦找到前一個節點，我們可以將新節點的指針指向前一個節點的下一個節點，然後將前一個節點的指針指向新節點。

這樣，新節點就被成功地插入到了指定位置，並且鍊錶的連續性得到了保持。

插入節點操作允許我們在鍊錶中的任何位置插入新的數據，這在處理鍊錶時非常有用喔!

void Solution :: insertNode(int seatNumber, int val){
    ListNode *newNode = new ListNode(val);
    ListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }

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

反轉

透過leetcode來實際說明如何刪除節點吧!

206. Reverse Linked List 

難度：Easy

題目說明

給定一個單向鍊錶，請反轉它並返回新的鍊錶。

想法

1. 反轉一個鍊錶實際上是將每個節點的指針方向反轉。
   
2. 在這個過程中，我們需要追蹤三個指標：
   • 目前節點：我們知道當前正在處理的節點。
   • 下一個節點：我們需要記錄當前節點的下一個節點，以便在反轉後將當前節點的指針指向它。
   • 前一個節點：我們需要記錄反轉後的新頭節點。

通過這三個指標的協同工作，我們可以逐個節點地改變其指向，最終實現整個鍊錶的反轉拉!

讓我們透過圖示來更詳細地說明反轉鍊錶的過程

1. 指向要處理的節點： 我們首先需要指向要處理的當前節點。
   
2. 記錄原先的下一個節點： 為了保持鍊錶的連續性，我們需要一個指標來記錄原先的下一個節點是誰，以便在反轉後重新指向它，使鍊錶不會斷開。
   
3. 指向前一個節點： 我們需要一個指標來指向前一個節點，因為在反轉時，當前節點的指針將指向前一個節點，而不是原先的下一個節點。
   
4. 移動到下一個節點： 需要注意的是，直接移動到下一個節點可能會使當前節點失去對原先下一個節點的引用。因此，在移動之前，我們需要有一個指標指向當前節點，以便後續操作能夠準確地找到它。
   
5. 重複動作： 重複上述步驟，直到當前指標指向鍊錶的結尾，表示反轉操作已完成。
   

這個反轉過程確保了鍊錶中每個節點的指針方向都被正確調整。這是一個在處理鍊錶的問題時非常實用且基本的技巧，它在解決各種鍊錶相關問題時都會派上用場。簡而言之，這種操作就像是把鍊錶裡的元素倒過來，非常有用！

完整程式碼:

/**
 * 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* reverseList(ListNode* head) {
        ListNode *current = head;
        ListNode *prev = nullptr;
        ListNode *next = nullptr;
        while(current != nullptr){
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }
};

刪除節點

透過leetcode來實際說明如何刪除節點

203. Remove Linked List Elements

難度：Easy

題目說明

刪除鍊錶中包含val 的所有節點，並返回新的頭。

想法

1. 如果下一個節點的值等於要刪除的值 val，則將下一個節點指向下下個節點，跳過要刪除的節點。
   
2. 為了確保鍊錶的頭節點的值也被考慮到，我們可以在鍊錶前添加一個假的節點，讓它的下一個節點指向原始的頭節點。
   
3. 使用一個指標來遍歷所有節點，從假的節點開始，如果遇到需要刪除的值，則執行刪除操作。
   
4. 最後，返回假的節點的下一個節點作為新的鍊錶的頭。
   

最後，我們來呈現完整的單向鏈結串列程式碼

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


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 {
    private :
        ListNode *head;
    
    public:
        Solution(){
            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 Solution::addNode_front(int val){
    ListNode *newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

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

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

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

void Solution :: insertNode(int seatNumber, int val){
    ListNode *newNode = new ListNode(val);
    ListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }

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

void Solution :: Reverse(){
    if (head == nullptr)
        return;
        
    ListNode *current = head;
    ListNode *prev = nullptr;
    ListNode *next = current->next;
    while ( current != nullptr){
        current->next = prev;
        prev = current;
        current = next;
        if (next != nullptr)
            next = current->next;
    }
    head = prev; 
}
int main(){
    Solution data;
    data.addNode_back(1);
    data.addNode_back(2);
    data.addNode_back(3);

    data.outputNode();

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

    data.addNode_front(4);
    data.outputNode();

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

    data.Reverse();
    data.outputNode();

    return 0;
    
}

預期今天會很忙，所以凌晨先來發文~

相信自己的選擇，不要因為別人認為毫無意義而氣餒。或許對別人來說無用，但只要你深信，它就對你有價值。