---
# System prepended metadata

title: 02. Linked List
tags: [LeetCode筆記]

---

# Linked List

###### tags: `LeetCode筆記`

### singly linked list
![](https://i.imgur.com/gVLy2wX.png)

### doubly linked list
![](https://i.imgur.com/jeb15oc.png)

## :memo: 基本的struct如何定義要寫好

### I. singly linked list
```
struct Node {
    int data;
    struct Node* next;
};

用typedef去自訂型別名稱的關鍵字
typedef struct node {
    int val;
    struct node* next;
} MyLinkedList;
MyLinkedList* head = NULL;
```
### II. doubly linked list
```
struct node {
    int val;
    struct node* prev; 
    struct node* next;
};
typedef struct node node_s;

typedef struct {
    int size;
    node_s* head;
    node_s* tail;
} MyLinkedList;
```

## :memo: 在宣告動態struct指標值，每一個element都要有初始值
```
struct node* newnode = (struct node*) malloc(sizeof(struct node));
newnode->val = 0;
newnode->next = NULL;
```

## :memo: 如何分配動態指標陣列 pointers[i]
```
struct node* pointers[size];
for (int i = 0; i < size; i++)
{
    pointers[i] = (struct node*) malloc(sizeof(struct node));
    pointers[i]->val = 0;
    pointers[i]->next = NULL;
}
每一個i都要分配memory及給初始值(尤其是NULL)
```

## int* 可以指向 struct node 嗎？
> ❌ 不可以。

## :memo: 在Add,Delete要畫圖協助分析
> 注意:
> 1. 某變數現在在哪個node
> 2. ->代表"變數->next"
> 3. 盡量用不同顏色的pen去trace code

## :memo: 設計演算法時要點
**如果if太多或一直為了error case去加if的話，就要重新擬定思考新的演算法**

## :memo: 不要把問題複雜化

## :memo: 要去計算時間和空間複雜度

## :memo: 經典問題
* Reverse Linked List
* Palindrome Linked List

## :memo: 在submit前先run題目的所有case

## :memo: 在Doubly Linked List要照顧到兩個箭頭

## :memo: Tips
- Always examine if the node is null before call the next field.
(**node->next的node不能是NULL**)
- Carefully define the end condition of your loop.
- Free to use several pointers.
- in singly linked list should store the previous node

## :memo: 一、Design Doubly Linked List C

### Node
```
struct node {
    int val;
    struct node* prev; 
    struct node* next;
};
typedef struct node node_s;

typedef struct {
    int size;
    node_s* head;
    node_s* tail;
} MyLinkedList;
```

### Initial a new linked list
```
node_s* createNode(int val) {
    node_s* newNode = malloc(sizeof(node_s));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->val = val;
    return newNode;
}


MyLinkedList* myLinkedListCreate() {
    MyLinkedList* myList = malloc(sizeof(MyLinkedList));
    myList->head = NULL;
    myList->tail = NULL;
    myList->size = 0;
    return myList;
}
```

### Traverse the linked list to get element by index
```
int myLinkedListGet(MyLinkedList* obj, int index) {
    node_s* tmp = obj->head;
    for (int i = 0; i < index && tmp != NULL; ++i) 
    {
        tmp = tmp->next;
    }

    return tmp != NULL ? (tmp->val) : -1;
}
```

### Add a new node at Head
```
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    node_s* newNode = createNode(val);
    // case 1: tail != NULL list is not empty
    // case 2: tail == NULL list is empty
    if (obj->tail != NULL) 
    {
        // just update the head
        newNode->next = obj->head;
        obj->head->prev = newNode;
        obj->head = newNode;
    } 
    else 
    {    
        // list is empty, update the tail as well
        obj->head = newNode;
        obj->tail = newNode;
    }

    obj->size++;
}
```

### Add a new node at Tail
```
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    node_s* newNode = createNode(val);
    // case 1: head != NULL list is not empty
    // case 2: head == NULL list is empty
    if (obj->head != NULL) 
    {
        obj->tail->next = newNode;
        newNode->prev = obj->tail;
        obj->tail = newNode;
    } 
    else 
    {
        obj->head = newNode;
        obj->tail = newNode;
    }

    obj->size++;
}
```

### Add a new node at Index
```
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if (index == obj->size) 
    {
        return myLinkedListAddAtTail(obj, val);
    } 
    else if (index == 0) 
    {    
        return myLinkedListAddAtHead(obj, val);
    }

    node_s* newNode = createNode(val);
    node_s* tmp = obj->head;
    for (int i = 0; i < index - 1 && tmp != NULL; ++i) 
    {
        tmp = tmp->next;
    }

    if (tmp != NULL) 
    {
        node_s* next = tmp->next;
        if (next != NULL) 
        {
            newNode->next = next;
            next->prev = newNode;
        }
        tmp->next = newNode;
        newNode->prev = tmp;
    }

    obj->size++;
}
```

### Delete a node at Index(head, index, tail)
```
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    node_s* tmp = obj->head;
    for (int i = 0; i < index && tmp != NULL; ++i) 
    {
        tmp = tmp->next;
    }

    if (tmp != NULL) 
    {
        node_s* prev = tmp->prev;
        node_s* next = tmp->next;

        if (prev != NULL)
        {
            // drop the node
            prev->next = next;
        }

        if (next != NULL) 
        {
            next->prev = prev;
        }

        if (tmp == obj->head) 
        {
            // move the head to next;
            obj->head = next;
        }    

        if (tmp == obj->tail) 
        {
            // move the tail to the previous
            obj->tail = prev;
        }

        free(tmp);
        obj->size--;
    }
}
```

### Free memory
```
void myLinkedListFree(MyLinkedList* obj) {
    node_s* cur = obj->head;
    node_s* tmp = NULL;
    while (cur != NULL) 
    {
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
}
```

## :memo: 二、Design Singly Linked List C++

### Node
```
// Definition for singly-linked list.
struct SinglyListNode {
    int val;
    SinglyListNode *next;
    SinglyListNode(int x) : val(x), next(NULL) {}
};

SinglyListNode* newnode = new SinglyListNode(val);
```

### Initial a new linked list
```
class MyLinkedList {
private:
    SinglyListNode *head;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = NULL;
    }
};
```

### Traverse the linked list to get element by index
```
/** Helper function to return the index-th node in the linked list. */
SinglyListNode* getNode(int index) {
    SinglyListNode *cur = head;
    for (int i = 0; i < index && cur; ++i) {
        cur = cur->next;
    }
    return cur;
}
/** Helper function to return the last node in the linked list. */
SinglyListNode* getTail() {
    SinglyListNode *cur = head;
    while (cur && cur->next) {
        cur = cur->next;
    }
    return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
    SinglyListNode *cur = getNode(index);
    return cur == NULL ? -1 : cur->val;
}
```

### Add a new node at Head
```
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
    SinglyListNode *cur = new SinglyListNode(val);
    cur->next = head;
    head = cur;
    return;
}
```

### Add a new node at Tail
```
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
    if (head == NULL) {
        addAtHead(val);
        return;
    }
    SinglyListNode *prev = getTail();
    SinglyListNode *cur = new SinglyListNode(val);
    prev->next = cur;
}
```

### Add a new node at Index
```
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
    if (index == 0) {
        addAtHead(val);
        return;
    }
    SinglyListNode *prev = getNode(index - 1);
    if (prev == NULL) {
        return;
    }
    SinglyListNode *cur = new SinglyListNode(val);
    SinglyListNode *next = prev->next;
    cur->next = next;
    prev->next = cur;
}
```

### Delete a node at Index(head, index, tail)
```
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
    SinglyListNode *cur = getNode(index);
    if (cur == NULL) {
        return;
    }
    SinglyListNode *next = cur->next;
    if (index == 0) {
        // modify head when deleting the first node.
        head = next;
    } else {
        SinglyListNode *prev = getNode(index - 1);
        prev->next = next;
    }
}
```

### Free memory
```
/*
    Default destructor only deletes head and size (allocated by constructor)
    We need destructor to free the memory used by all individual nodes
*/
// Destructor
~MyLinkedList()
{
    Node *p = head;
    // Delete node at head while head is not null
    while (head != nullptr)
    {
        head = head->next;
        delete p;
        p = head;
    }
}
```

## :memo: 三、Two Pointers Technique
1. Two pointers starts at different position: one starts **at the beginning** while another starts **at the end**;
2. Two pointers are moved at different speed: one is **faster** while another one might be **slower**.

* Let's start with a classic problem:
     * Given a linked list, **determine if it has a cycle in it.**
         * If there is no cycle, the fast pointer will stop at the end of the linked list.
        * If there is a cycle, the fast pointer will eventually meet with the slow pointer.

## :memo: Linked List Cycle (Easy) 只是判斷圈
![](https://i.imgur.com/TRwPOZP.png)

![](https://i.imgur.com/0cQRx8W.png)

### 作法 fast and slow pointer
one-step pointer and two-steps pointer run on the linked list.
遇到就是圈，不遇就沒圈。
```
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fastptr = nullptr;
        ListNode* slowptr = nullptr;
        
        if (head == nullptr) {
            return false;
        }
        
        fastptr = head;
        slowptr = head;
        
        // 是由快的pointer去決定跳出while
        while (fastptr != nullptr && fastptr->next != nullptr) {

            fastptr = fastptr->next->next;
            slowptr = slowptr->next;
            
            if (fastptr == slowptr) {
                return true;
            }
        }
        
        return false;
    }
};
```

## :memo: Linked List Cycle II (Medium) 要決定在哪個node是tail指向的節點
![](https://i.imgur.com/TRwPOZP.png)

![](https://i.imgur.com/7ktky1q.png)

### 作法 Floyd's Tortoise and Hare
tortoise = head
hare = head
tortoise 跑one-step
hare 跑two-steps
ptr1 = head
ptr2 = intersect
ptr1 跑one-step
ptr2 跑one-step
要分兩階段，第一階段用龜兔找出相會點，再將相會點assign給ptr2，然後ptr1從head開始跑，再次相遇的點就是答案
```
class Solution {
private:
    ListNode* getIntersect(ListNode* head) {
        ListNode* tortoise = head;
        ListNode* hare = head;
        
        while (hare != nullptr && hare->next != nullptr) {
            tortoise = tortoise->next;
            hare = hare->next->next;
            if (tortoise == hare) {
                return tortoise;
            }
        }
        
        return nullptr;
    }
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        ListNode* intersect = getIntersect(head);
        if (intersect == nullptr) {
            return nullptr;
        }
        
        ListNode* ptr1 = head;
        ListNode* ptr2 = intersect;
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        
        return ptr1;
    }
};
```

## :memo: Intersection of Two Linked Lists (Easy)
![](https://i.imgur.com/mx9Hu8L.png)

**Input:** intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
**Output:** Intersected at '8'
**Explanation:** The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

### 作法
![](https://i.imgur.com/iDvAU0w.png)
如果pointerA跑到底了，就把pointerA指向HeadB去跑b，如果pointerB跑到底了，就把pointerB指向HeadA去跑a，這樣兩個pointers都有跑到a+b+c就是Intersection
```
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        while (ptrA != ptrB) {
            ptrA = ptrA == nullptr ? headB : ptrA->next;
            ptrB = ptrB == nullptr ? headA : ptrB->next;
        }
        
        return ptrA;
    }
};
```

## :memo: Remove Linked List Elements (Easy)
![](https://i.imgur.com/B34MdZv.png)

![](https://i.imgur.com/tGi6Nxt.png)

### 作法 Sentinel Node
ListNode* sentinel = new ListNode(0); //dummy效果
ListNode* toDelete = nullptr; //用來指向要刪的node
```
    ListNode* sentinel = new ListNode(0);
    sentinel->next = head;

    ListNode* prev = sentinel;
    ListNode* curr = head;
    ListNode* toDelete = nullptr;

    while (curr != nullptr) {
        if (curr->val == val) {
            prev->next = curr->next;
            toDelete = curr;
        } else {
            prev = curr;
        }

        curr = curr->next;

        if (toDelete != nullptr) {
            delete toDelete;
            toDelete = nullptr;
        }
    }

    ListNode* ret = sentinel->next;
    delete sentinel;
    return ret;
```
### 作法 prev,curr, 3個if
直覺的作法
3種情況
```
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        if (head->val == val) {
            head = head->next;
            curr = curr->next;
        }
        else if (curr->val == val) {
            prev->next = curr->next;
            curr = curr->next;
        }
        else {
            prev = curr;
            curr = curr->next;
        }
    }

    return head;
```

## :memo: Remove Nth Node From End of List (Medium)
![](https://i.imgur.com/EniDxYH.png)

![](https://i.imgur.com/FJBFQEt.png)

### 作法 dummy node
![](https://hackmd.io/_uploads/S1OQqDbA3.png)

```
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* ptr1 = dummy;
        ListNode* ptr2 = dummy;
        
        for (int i = 1; i <= n + 1; i++) {
            ptr1 = ptr1->next;
        }
        
        while (ptr1 != nullptr) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        
        ptr2->next = ptr2->next->next;
        
        return dummy->next;   // head不行
    }
};
```

### 作法
數link list的長度，再去找欲刪去Node的前一個Node，如果是第一項就回傳head->next
```
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* curr;
        
        int size = 0;
        curr = head;
        while (curr != nullptr) {
            curr = curr->next;
            size++;
        }
        
        curr = head;
        int i = 0;
        while (i < size - 1 - n) {
            curr = curr->next;
            i++;
        }

        if (size == n) {
            return curr->next;
        }
        else if (curr->next != nullptr) {
            curr->next = curr->next->next;    
        }
        
        return head;
    }
};
```

## :memo: *Reverse Linked List (Easy)
![](https://i.imgur.com/dmw7nDN.png)

![](https://i.imgur.com/kcuzPgU.png)

### 作法 iteration
這題要做的就是改變next箭頭的方向
1.next就是curr的箭頭指向右的節點
2.將curr的箭頭從右轉向左指向prev
3.curr asign給 prev
4.next asign給 curr
**時間: O(N)**
**空間: O(1)**
```
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        ListNode* next = head;

        while (current != nullptr) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
    }
};
```
### 作法 recursion
**時間: O(N)**
**空間: O(N)**
```
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};
```

## :memo: *Reverse Linked List II (Medium)
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

![](https://hackmd.io/_uploads/Bk-pvbuza.png)

### 作法
```
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        vector<int> box(right - left + 1, 0);

        ListNode* p = head;
        ListNode* q = head;
        int i = 1;
        while (i <= right) {
            if (i >= left) {
                box[i - left] = p->val;
            }            
            p = p->next;
            i++;
        }
        i = 1;
        while (i <= right) {
            if (i >= left) {
                q->val = box[right - i];
            }
            q = q->next;
            i++;
        }

        return head;
    }
};
```

## :memo: Odd Even Linked List (Medium)
![](https://i.imgur.com/W3fGUdp.png)

![](https://i.imgur.com/bfIVBig.png)

### 作法
我寫了笨方法用了矩陣去存空間花了O(N)，
解答只有空間花O(1)如下
```
if (head == nullptr) {
    return nullptr;
}

ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;

while (even != nullptr && even->next != nullptr) {
    odd->next = even->next;
    odd = odd->next;
    even->next = odd->next;
    even = even->next;
}
odd->next = evenHead;

return head;
```

## :memo: *Palindrome Linked List (Easy)
![](https://i.imgur.com/NVQnxm7.png)

![](https://i.imgur.com/Sx1pSce.png)

### 作法 reverse linked list 和 fast and slow pointer
**空間: O(1)**

要用到兩個副程式:reverse,endOfFirstHalf(找前半)
步驟:
找到前半後，把後半reverse，之後一個個比，不同就回傳false，都相同後要先將後半reverse回來串到前半後再回傳true
```
class Solution {
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* next = head;
        
        while (curr != nullptr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }

private:
    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
    }
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }
        
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
        
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }
};
```

## :memo: 四、Comparison
![](https://i.imgur.com/Pposix6.png)

## :memo: Merge Two Sorted Lists (Easy)
![](https://i.imgur.com/HMcIoMX.png)

![](https://i.imgur.com/1QHb3ee.png)

### 作法 dummy node
用一個dummy node裝INT_MIN，再用指標tail指向dummy的位址，接著開始比較list1和list2，誰小tail就指向誰，並且該list前進，直到有一個list為nullptr，最後看剩誰就指向該list，最後回傳dummy.next(是點喔)
```
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {        
        ListNode dummy(INT_MIN);
        ListNode* tail = &dummy;
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;                
            }
            else {
                tail->next = list2;
                list2 = list2->next;                
            }
            tail = tail->next;
        }
        
        tail->next = list1 ? list1 : list2;
        return dummy.next;
    }
};
```

## :memo: Add Two Numbers (Medium)
![](https://i.imgur.com/Ya0gQWP.png)

![](https://i.imgur.com/Hg5cK4y.png)

### 作法 dummy node
**時間: O(max⁡(m,n))** Assume that m and n represents the length of l1 and l2 respectively, the algorithm above iterates at most max⁡(m,n) times.
**空間: O(max⁡(m,n))** The length of the new list is at most max⁡(m,n)+1.
```
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* curr = dummyHead;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int x = l1 ? l1->val : 0;
            int y = l2 ? l2->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        
        return dummyHead->next;
    }
};
```

## :memo: Add Two Numbers II (Medium)
You are given two **non-empty** linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

![image](https://hackmd.io/_uploads/SyqafK54p.png)

### 作法 Stack
完全沒想到Stack **QQ**
```
class Solution {
public:    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;

        while (l1 != nullptr) {
            s1.push(l1->val);
            l1 = l1->next;
        }

        while (l2 != nullptr) {
            s2.push(l2->val);
            l2 = l2->next;
        }

        int totalSum = 0, carry = 0;
        ListNode* ans = new ListNode();
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {
                totalSum += s1.top();
                s1.pop();
            }
            if (!s2.empty()) {
                totalSum += s2.top();
                s2.pop();
            }

            ans->val = totalSum % 10;
            carry = totalSum / 10;
            ListNode* newNode = new ListNode(carry);
            newNode->next = ans;
            ans = newNode;
            totalSum = carry;
        }

        return carry == 0 ? ans->next : ans;
    }
};
```

## :memo: Flatten a Multilevel Doubly Linked List (Medium)
![](https://i.imgur.com/iaszG1U.png)

![](https://i.imgur.com/nNtXSA9.png)

### 作法
利用child指標先暫存等等要back指標指的node
**空間: O(1)**
```
class Solution {
public:
    Node* flatten(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        Node* curr = head;
        Node* tail;
        while (curr != nullptr) {
            if (curr->child != nullptr) {
                Node* temp_ptr = curr->next;
                curr->next = curr->child;
                curr->child->prev = curr;
                curr->child = temp_ptr;
            }
            if (curr->next == nullptr) {
                tail = curr;
            }
            curr = curr->next;
        }

        Node* back_ptr = tail;
        while (back_ptr != nullptr) {
            if (back_ptr->child != nullptr) {
                cout<<back_ptr->child->val<<endl;
                Node* p = back_ptr->child;
                p->prev = tail;
                tail->next = p;
                back_ptr->child = nullptr;
                while (p->next != nullptr) {
                    p = p->next;
                }
                tail = p;
            }
            back_ptr = back_ptr->prev;
        }
        
        return head;
    }
};
```

## :memo: Insert into a Cyclic Sorted List (Medium)
![](https://i.imgur.com/ii6PgB0.png)

![](https://i.imgur.com/13xDnp8.png)

### 作法
![](https://i.imgur.com/L5VqtmU.png)

![](https://i.imgur.com/ROFW2MX.png)

![](https://i.imgur.com/TmMD0uO.png)

```
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (head == nullptr) {
            Node* newnode = new Node(insertVal);
            newnode->next = newnode;            
            return newnode;
        }

        Node* prev = head;
        Node* curr = head->next;
        bool toInsert = false;
        
        do {
            if (prev->val <= insertVal && insertVal <= curr->val) {
                // Case 1).
                toInsert = true;
            } 
            else if (prev->val > curr->val) {
                // Case 2).
                if (insertVal >= prev->val || insertVal <= curr->val) {
                    toInsert = true;
                }
            }
            
            if (toInsert) {
                prev->next = new Node(insertVal, curr);
                return head;
            }
            
            prev = curr;
            curr = curr->next;
        } while (prev != head);
            
        // Case 3).
        prev->next = new Node(insertVal, curr);
        return head;
    }
};
```

## :memo: Copy List with Random Pointer (Medium) Deep copy
![](https://i.imgur.com/0IiC7L7.png)

![](https://i.imgur.com/BHZtaA5.png)

### 作法
第一回合複製node在自己後面7->7->13->13->11->11->10->10->1->1
第二回合處理random指標
第三回合抽取複本
```
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* iter = head;
        Node* next;
        
        // First round: make copy of each node,
        // and link them together side-by-side in a single list.
        while (iter != nullptr) {
            next = iter->next;
            
            Node* copy = new Node(iter->val);
            iter->next = copy;
            copy->next = next;
            
            iter = next;
        }
        
        // Second round: assign random pointers for the copy nodes.
        iter = head;
        while (iter != nullptr) {
            if (iter->random != nullptr) {
                iter->next->random = iter->random->next;
            }
            iter = iter->next->next;
        }
        
        // Third round: restore the original list, and extract the copy list.
        iter = head;
        Node* pseudoHead = new Node(0);
        Node* copy;
        Node* copyIter = pseudoHead;        
        while (iter != nullptr) {
            next = iter->next->next;
            
            // extract the copy
            copy = iter->next;
            copyIter->next = copy;
            copyIter = copy;
            
            // restore the original list
            iter->next = next;
            
            iter = next;
        }
        
        return pseudoHead->next;        
    }
};
```

## :memo: Rotate List (Medium) 比較 Rotate Array (Medium)
![](https://i.imgur.com/A7mIgao.png)

![](https://i.imgur.com/FLj5FAD.png)

### 作法
第一個for找到舊的尾巴，之後再尾巴的next指向頭"變成一圈circular"，第二個for找到新的尾巴，然後新的頭是新的尾巴的next，再把新的尾巴指向nullptr，回傳new_head
```
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {       
        if (head == nullptr) {
            return nullptr;
        }
        
        if (head->next == nullptr) {
            return head;
        }
        
        ListNode* old_tail = head;
        for (int n = 1 ; old_tail->next != nullptr; n++) {
            old_tail = old_tail->next;
        }
        old_tail->next = head;
        
        ListNode* new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++) {
            new_tail = new_tail->next;
        }
        ListNode* new_head = new_tail->next;
        
        new_tail->next = nullptr;
        
        return new_head;
    }
};
```

## :memo: 刷題檢討
**在回傳Linked List的最後一個node要指向nullptr!!!!!**
**25. Add Two Numbers**那題寫得很不好
**章節分類:**
1.Singly Linked List
2.Two Pointer Technique
*3.Classic Problems
4.Doubly Linked List
5.Conclusion
**技巧:**
1. dummy node
2. feel free to use several pointers at the same time.
3. in many cases, you need to track the previous node of the current node.