剩下 Circular Link List 就要講完Link List了，加油!
今天有相關的Leetcode了。同樣的，我用兩題來做實練。
文章會複習有三種常見的Link List的比較，一樣想直接看的可以直接跳過去。

最後，讓我們談談具有一個特殊性質的單向鏈結串列：環形鏈結串列。

什麼樣子才算是環狀鏈結串列

環狀鏈結串列是指最後一個節點的指針指向第一個節點，形成一個閉環。
優點：無論從哪一個節點開始尋找，並訂能夠經過所有節點。
缺點：當操作不當時，循環鍊錶可能導致無限循環，使得程序進入死循環。因此，在使用循環鍊錶時需要特別謹慎。

相信大家看了這麼多，已經不用我在分開解釋了。
與Single Link List 相似，只是要注意 最尾端要連到頭

完整程式碼

#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 CircularLinkList{
     private :
         ListNode *head;
         int size;
     
     public:
         CircularLinkList(){
            head = nullptr;
            size = 0;
         }
         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 CircularLinkList::addNode_front(int val){
    ListNode *newNode = new ListNode(val);
    newNode->next = head;
    if(head != nullptr){
        ListNode *current = head;
        while(current->next != head){
            current = current->next;
        }
        current->next = newNode;
    }
    else{
        newNode->next = newNode;
    }
    head = newNode;
    size++;
}

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

void CircularLinkList::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;
    size--;
}

void CircularLinkList::outputNode(){
    ListNode *current = head;
    for (int i=0; i< size+1; i++){
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
}

void CircularLinkList::insertNode(int seatNumber, int val){
    ListNode *newNode = new ListNode(val);
    ListNode *current = head;
    if(head == nullptr){
        head = newNode;
        return;
    }
    for(int i=0; i<seatNumber-1; i++){
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
    size++;
}

void CircularLinkList::Reverse(){
    ListNode *current = head;
    ListNode *prev = nullptr;
    ListNode *next = nullptr;
    ListNode *temp = head;
    while(current->next != head){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    current->next = prev;
    head = current;
    temp->next = head;
}

int main(){
    CircularLinkList circularLinkList;
    circularLinkList.addNode_front(1);
    circularLinkList.addNode_front(2);
    circularLinkList.addNode_back(3);
    circularLinkList.addNode_back(4);
    
    circularLinkList.insertNode(2, 5);
    circularLinkList.outputNode();

    circularLinkList.Reverse();
    circularLinkList.outputNode();
}

Leetcode 挑戰

141. Linked List Cycle

程度

Easy

題目

判斷這個linked list是否循環。

想法

我們要檢查這條連結串列是否有循環，就好比跑步者在操場上跑圈一樣。如果你被超過一圈，那就表示你被「倒追」了，因為對方跑得比你快，已經趕上你了。這個連結串列也是一樣，看看是否有一個節點被其他節點「倒追」，也就是被追趕上，這樣就表示連結串列是循環的。。

因此我們只要設計兩個跑者一個跑比較快，一個跑比較慢就解決啦!

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != NULL && fast ->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

142. Linked List Cycle II

程度

Medium

題目

傳回循環開始的節點

想法

1. 設計兩個跑者一個跑比較快，一個跑比較慢，兩個人一起跑值到他們相遇
2. 推導數學公式，看能不能找到方法。
   

讓我們來試試吧 (圖好醜請見諒)

1. 假設 : 跑比較快的為P1； 跑比較慢的為P2。
   因為他們同時從A點出發到C點相遇，此時由於比較快的跑者跑了兩倍的路程，所以可以得知

• 表示開始循環之前鍊錶的長度
• 表示從循環開始到相遇的距離。

2. 當它們相遇時，P2 行進 步，同時P1 行進 2 步。
   而此是已經繞了N圈 也就是說兩者相差有N圈。
   數學表示為:
   

我們可以得知一些信息

1. 。 這也代表說 P1 走的距離 等同於N圈
2. 由於我們想知道A到B的距離且 所以，

• 
• 移項後變成

由圖以及 可以看出，如果相遇後，在找一個人P3一次走一步的話，當P3 走 距離，此時P2也會繞道B點。真是神奇!

程式碼:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != NULL && fast ->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                break;
        }
        if (fast == NULL || fast ->next == NULL)
            return NULL;
        if(fast != slow)
            return NULL;
        ListNode *newfriend = head;
        while(newfriend != slow){
            slow = slow->next;
            newfriend = newfriend->next;
            if(slow == newfriend)
                break;
        }
        return newfriend;
    }
};

最後讓我們複習一下鏈結串列（Link List）

優點

1. 動態連結資料 : 不需要一個完整的大空間。
2. 動態大小調整: 不需要先配置記憶體大小，只在需要適時分配記憶體，這有助於節省內存。
3. 插入和刪除效率高: 只需要調整指標，不需要移動大量元素。

缺點

1.存取時間複雜: 不像陣列能直接所引到該位置，必須一個找一個。
2.佔用額外記憶體: 需要有指標儲存要串起來的下一個資料的位置。
現在，讓我們建立一個比較表

每種Link List都有其特殊性和特點，選擇哪種類型的Link List取決於特定的應用需求喔!

為了怕週四分心在這裡，這是一篇事先預留好的文章 ，所以至於文章的結語只能等到當日才有心得
面對有的時候並不是一場可怕的挑戰，而是一個成長的機會。它可以幫助我們變得更強大，發現內在的勇氣，並拓展我們的視野。