<style>
.easy{
color:green;
}
.medium{
color:#eda35e;
}
.red{
color:red;
}
</style>
# Linked List
## :speech_balloon: 介紹
初學Ｃ++時常用Array儲存多筆資料，若欲進行新增與刪除Array第一個元素或最後一個元素需要$\ O(1)$ 時間，但刪除<span class="red">任意位置</span>卻需要$\ O(N)$時間，面臨時常增刪情況顯得很沒有效率，故相較Array而言List符合上述使用情境。
* Linked List
* Linked List 常見類別
* Single Linked List
* Double Linked List
* Circular Linked List
* Circular Double Linked List
* 特點
* 使用非連續記憶體位置
* 增刪任意節點只需$\ O(1)$
* 走訪任意節點需$\ O(N)$
* Stack、Tree、Queue可用Linked List實作
* 先備知識
* C++ program
* 文章分類
* 難度：★
## :book:內容
---
## Single Linked List
>一個**List**以**Node(節點)**為基礎單位，Node包含**資料值**與指向**下一個節點**的指標
* Node(節點)
```cpp=
template <class T> class List; //事先宣告List類別，才可讓Node知道有List這個Class
template <class T> //泛型
class Node {
friend class List
private:
T data; //資料值
Node<T>* nextNode; //下一個節點位置
public:
Node(int vaule): data(value), nextNode(NULL){}
}
```
* List(串列)
```cpp=
template <class T>
class List {
private:
Node<T>* root;
public:
List(): root(NULL) {}
Node<T>* findNode(int position); //回傳節點節點位置
void insertNode(int position, int value); //插入節點
void deleteNode(int position); //刪除節點
}
```
### 新增
>初始狀態
* **從頭新增**
* newNode指向第一個Node
* Root指向newNode
* **從尾新增**
* 最後一個Node指向新的Node
* **從中間新增**
* newNode指向右邊節點
* 左邊節點指向newNode
:::success
:bulb: 實作小技巧
newNode優先處理，先不要動到其他原本指標，以免遺失Node
:::
### 刪除
>初始狀態
* **從頭刪除**
* Root指向下一個節點
* 回收第一個節點
* **從尾刪除**
* 先用temp pointer指向要刪除的節點
* 要刪除的左邊節點指向Null
* 回收節點
* **中間刪除**
* 先用temp pointer指向要刪除的節點
* 要刪除的左邊節點指向下一個節點
* 回收節點
## Double Linked List
> 原本只有指向單邊的Single Linked List多了指向左邊的Pointer
## Circular Linked List
> 原本只有指向單邊的Single Linked List多了指向第一個節點的Pointer
>
## Circular Double Linked List
> 原本的Circular Linked List，新增Double Linked List的特點
## LeetCode練習範例
### Delete the Middle Node of a Linked List <span class="medium">(medium)</span>
---
>You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
>The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
>For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
```cpp=
/**
* 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* deleteMiddle(ListNode* head) {
int count = 0;
ListNode* temp = head;
ListNode* result;
for(;temp != NULL; temp = temp->next, count++);
int middle = count / 2;
temp = head;
for(int i = 0; i < middle - 1; i++, temp = temp->next);
if(temp->next) {
temp->next = temp->next->next;
}
if(count == 1) head = NULL;
return head;
}
};
```
### Odd Even Linked List <span class="medium">(medium)</span>
---
>Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
>
>The first node is considered odd, and the second node is even, and so on.
>
>Note that the relative order inside both the even and odd groups should remain as it was in the input.
>
>You must solve the problem in O(1) extra space complexity and O(n) time complexity.
```cpp=
/**
* 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* oddEvenList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* even_head = even;
while(odd->next != NULL && even->next != NULL) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = even_head;
return head;
}
};
```
### Reverse Linked List <span class="easy">(easy)</span>
---
>Given the head of a singly linked list, reverse the list, and return the reversed list.
```cpp=
/**
* 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* previous = NULL;
ListNode* current = head;
while(current){
ListNode* temp = previous;
previous = current;
current = current->next;
previous->next = temp;
}
head = previous;
return head;
}
};
```
### Maximum Twin Sum of a Linked List <span class="medium">(medium)</span>
>In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.
>
>For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
>
>The twin sum is defined as the sum of a node and its twin.
>
>Given the head of a linked list with even length, return the maximum twin sum of the linked list.
:::warning
:bulb: 解題想法
:::
```cpp=
/**
* 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* it){
ListNode* previous = NULL;
ListNode* current = it;
cout << it << endl;
while(current) {
ListNode* r = previous;
previous = current;
current = current->next;
previous->next = r;
}
return previous;
}
int pairSum(ListNode* head) {
ListNode* left_it = head;
//in order to get right half first pointer
// so right_it points at first element
ListNode* right_it = head;
while(right_it && right_it->next) {
left_it = left_it->next; //move one pace
right_it = right_it->next->next; //move two paces
}
ListNode* right_half = reverseList(left_it);
cout << right_half << endl;
int max = 0;
while(right_half) {
int sum = head->val + right_half->val;
if(sum > max) max = sum;
right_half = right_half->next;
head = head->next;
}
return max;
}
};
```
## Circular Double Linked List Implement
> 這個是我在練習OJ題目時，自己寫出來的template，如果對實作毫無頭緒可以參考看看
[NTHU OJ 14053](https://acm.cs.nthu.edu.tw/problem/14053/)
```cpp=
#include <iostream>
#define err(a) cout << #a << " " << a << endl;
using namespace std;
template <class T> class Chain;
template <class T>
class Node {
friend class Chain<T>;
private:
Node<T>* left;
Node<T>* right;
T data;
public:
Node(int value):left(NULL), right(NULL), data(value){}
};
template <class T>
class Chain {
private:
Node<T>* root;
int index;
public:
Chain(): root(NULL), index(-1){}
Node<T>* findNode(int pos) {
Node<T>* it = root;
if(pos >= 0) {
for (int i = 0; i != pos && it != NULL; i++, it = it->right);
}
else{
for (int i = 0; i != pos && it != NULL; i--, it = it->left);
}
return it;
}
void insertNode(int pos, T value) {
Node<T>* it;
Node<T>* newNode = new Node<T>(value);
index ++;
if(root == NULL) {
root = newNode;
root->right = root;
root->left = root;
return;
}
if(pos == -1) {
it = findNode(-1);
}
else{
it = findNode(pos-1);
}
newNode->left = it;
newNode->right = it->right;
it->right->left = newNode;
it->right = newNode;
if(pos == 0) {
root = newNode;
}
}
void deleteNode(int pos, int m) {
Node<T>* it = findNode(pos);
it->left->right = it->right;
it->right->left = it->left;
if (it->data >= m) {
insertNode(-1, it->data);
if(pos == 0) {
root = root->right;
}
}
else {
if(pos == 0) {
root = root->right;
}
delete it;
it = NULL;
}
index--;
}
void showNode(int v1, int v2) {
Node<T>* it = findNode(v1);
if(it == NULL) return;
if(v1 <= v2) {
for(int i = v1; i < v2 && it != NULL; i++, it = it->right){
cout << it->data << " ";
}
if(it) cout << it->data << " " << endl;
}
else{
for(int i = v1; i > v2 && it != NULL; i--, it = it->left) {
cout << it->data << " ";
}
if(it) cout << it->data << " " << endl;
}
}
void printNode() {
cout << "===ALL====" << endl;
showNode(0, index);
cout << "===" << endl;
}
};
int main() {
Chain<int> chain;
char c;
int v1, v2;
while(cin >> c >> v1 >> v2) {
switch (c)
{
case 'i':
chain.insertNode(v1, v2);
//chain.printNode();
break;
case 'd':
chain.deleteNode(v1, v2);
break;
case 's':
chain.showNode(v1, v2);
break;
default:
break;
}
}
}
```
###### tags: `LeetCode 75` `DataStructure`
Sign in with Wallet
Connect another wallet