---
title: 題解：鏈結串列 Linked List
tags: solution
---

# [LeetCode] 237 - Delete Node in a Linked List
- 題目連結：[237 - Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)

void deleteNode(ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

---
# [LeetCode] 21 - Merge Two Sorted Lists
- 題目連結：[21 - Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

開一個新的list，並把兩串list給合併，
下面用了一個很值得參考的邏輯寫法，之後介紹「Merge Sort」時也會看到這樣的寫法：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

    ListNode* head = new ListNode();
    ListNode* cur = head;

    while(l1 != nullptr || l2 != nullptr){
        if(l1 != nullptr && l2 == nullptr || l1->val < l2->val){
            cur = cur->next = new ListNode(l1->val);
            l1 = l1->next;
        }
        else{
            cur = cur->next = new ListNode(l2->val);
            l2 = l2->next;
        }
    }
    return head->next;
}

---
# [Geeks] Doubly linked list Insertion at given position
- 題目連結：[Doubly linked list Insertion at given position](https://practice.geeksforgeeks.org/problems/insert-a-node-in-doubly-linked-list/1)

void addNode(Node *head, int pos, int data) {
    while(pos--)
       head = head->next;
    
    Node *temp = new Node(data);
    temp->prev = head;
    temp->next = head->next;
    head->next = temp;
}

---
# [Geeks] Delete node in Doubly Linked List
- 題目連結：[Delete node in Doubly Linked List](https://practice.geeksforgeeks.org/problems/delete-node-in-doubly-linked-list/1)

Node* deleteNode(Node *head, int x) {
    if(x==1)
        return head->next;
        
    Node *cur = head;
    while(--x)
        cur = cur->next;

    cur->prev->next = cur->next;
    return head;
}

---
# [LeetCode] 141 - Linked List Cycle
- 題目連結：[141 - Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)

我們可以將val設定成一個超出範圍的值( $[-10^5,10^5]$ )，這樣就可以記錄該點是否有被走過了。

bool hasCycle(ListNode *head) {

    while(head != NULL){
        if(head->val == 100005)
            return true;
        head->val = 100005;
        head = head->next;
    }
    
    return false;
}

---
# [CSES] Josephus Problem I
- 題目連結：[Josephus Problem I](https://cses.fi/problemset/task/2162)

這一題的正確解法並不是用串列來解，
但是這題由於跳過的數量小，故亦可利用Circlular Linked List來解 (~~當做練習~~)。

利用單向串列來解，建構完後將頭尾進行相接 (圖例中是將8接到1)：


接下來，從1開始數，跳過(skip)1人並移出(rm=remove)1人，直到剩下最後1人為止：


( 此圖之移出順序為：2, 4, 6, 8, 3, 7, 5, 1 )

Linked List version ( Time: 0.04s ) :

# include <bits/stdc++.h>
using namespace std;
 
struct Node{
    int num;
    Node* ptr;
 
    Node(Node *p, const int &n){
        num = n;
        ptr = p;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    Node* llist;
 
    int N,n;
    cin>>N;
    Node *head = new Node(nullptr,1);
    Node *cur = head;
 
    // building circular linked list
    for(n = 2 ; n<=N ; n++)
        cur = cur->ptr = new Node(nullptr,n);
    cur->ptr = head;
 
    // traversing
    while(--N){
        cur = cur->ptr;
        cout<<cur->ptr->num<<' ';
        cur->ptr = cur->ptr->ptr;
    }
    cout<<cur->num;
}

Array version ( Time: 0.03s ) :

# include <bits/stdc++.h>
using namespace std;
 
struct Node{
    int num;
    int next;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int N,n;
    cin>>N;
    Node k[200005];
 
    // building circular list
    k[1].num = 1;
    for(n = 2 ; n<=N ; n++){
        k[n].num = n;
        k[n-1].next = n;
    }
    k[N].next = 1;
    
    
    // traversing (total move N times)
    n = 1;
    while(N--){
        cout<<k[k[n].next].num<<' ';
        n = k[n].next = k[k[n].next].next;
    }
}

> 為什麼用陣列來寫會比用指標來寫還要快呢？
> 其實執行的時間就只差在「建構(building circlular list)」的步驟而已。
>
> 這是結論：new 的執行速度會比直接宣告變數的執行速度還要來得慢
>
> 文章參考：[Why should C++ programmers minimize use of 'new'?](https://stackoverflow.com/questions/6500313/why-should-c-programmers-minimize-use-of-new)

以下是幾個網路上看到非常有意思的解法：
- 數學解(圓)：[How to cheat death — Josephus Problem](https://medium.com/@RahulDharan/how-to-cheat-death-josephus-problem-ae31d37af7ed)
- 動態規劃解法：[GeeksforGeeks - Josephus problem | Set 1 (A O(n) Solution)](https://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/)
- Wiki：[約瑟夫斯問題](https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98) (推導動態規劃解與另一種的數學解)

---
# [LeetCode] 938 - Range Sum of BST
- 題目連結：[938 - Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)

利用遞迴的方式，把每個節點看成有左和右 這兩個分支，
若這個節點符合題目要求的範圍，則將節點上的值回傳回去。

可以看成一個簡單的遞迴式子：

$f(x)=\begin{cases}
0 &\text{if } x=\text{null} \\
f(x_{\text{left}}) + f(x_{\text{right}}) + x_{\text{val}} & \text{if }x_{\text{val}} \in[\text{low, high}] \\
f(x_{\text{left}}) + f(x_{\text{right}}) & \text{if }x_{\text{val}} ∉[\text{low, high}] \\
\end{cases}$

int rangeSumBST(const TreeNode* root, int low, int high) {
    if(root == nullptr)
        return 0;

    return ((low <= root->val && root->val <= high) ? root->val : 0) +
           rangeSumBST(root->left,low,high) + rangeSumBST(root->right,low,high);
    // current + left + right
    // if the current value on the interval [low,high], the result will be add.
}

###### posted date: `2021.4.8`