---
tags: tutor, Alisha
---
# 2022-02-17 四 2000-2200

[TOC]

## 連結
[Problem List - Alisha](https://hackmd.io/GELwljkET-uc6JgjEovuag?both)

[Replit](https://replit.com/join/bdmizyqqmi-chungholy)

## C C++ 分道揚鑣
C++ 與 C 之間相去越遠，兩者已經儼然是**不同的語言**了!
(Jserv 大師也曾說過 - 自 1999 年制訂的 C99 規格開始，C 語言和 C++ 程式語言就分道揚鑣，換言之「C++ 是 C 語言的超集 (super-set)」不再成立。)

[Linus Torvalds: “C++ is really a terrible language!”](https://medium.com/nerd-for-tech/linus-torvalds-c-is-really-a-terrible-language-2248b839bee3)

C++ 之父 - Bjarne Stroustrup 曾說過, "you should use vector over Array unless you have a really good reason to use an array"。因為記憶體的管理永遠是開發者的痛，在現今的程式開發中最好能避免使用new，因為這會使我們必須持續的追蹤其大小且須手動刪除釋放。尤其是在re-size array時，vector會更加好用。
當然不諱言的是，dynamic array的速度還是優於vector的，只是那是只在極端講求速度的class 的內部實作中才使用。

## 遞迴 Recursion
### 遞迴是什麼

[Binary, Hanoi and Sierpinski, part 1](https://www.youtube.com/watch?v=2SUvWfNJSsM)



電腦程式中，副程式**直接**或**間接**呼叫自己就稱為遞迴。也就是:
:::info
使用相同的方法，解決重複性的問題 (Recurrent Problems)。
:::

[遞迴 (Recursion)](https://notfalse.net/9/recursion#-direct-recursion)

遞迴算不上~~演算法~~，只是**程式流程控制**的一種。

程式的執行流程有兩種:
- 循序，分支(迴圈)
- 呼叫副程式(遞迴)

初學者為什麼覺得遞迴很難呢？因為他跟人類的思考模式不同，電腦的兩種思維模式：窮舉與遞迴(enumeration and recursion)，窮舉是我們熟悉的而遞迴是陌生的，而遞迴為何重要呢？因為他是思考好的演算法的起點，例如**分治**與**動態規劃**。

> 分治 (Divde and Conquer)：一刀均分左右，兩邊各自遞迴，返回重逢之日，真相合併之時。

分治 (Divide and Conquer) 是種運用遞迴的特性來設計演算法的策略。對於求某問題在輸入 S 的解 P(S) 時，我們先將 S 分割成兩個子集合 S1 與 S2，分別求其解 P(S1) 與 P(S2)，然後再將其合併得到最後的解 P(S)。要如何計算 P(S1) 與 P(S2) 呢？因為是相同問題較小的輸入，所以用遞迴來做就可以了。分治不一定要分成兩個，也可以分成多個

### 背後原理
[你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSJ6hRj-zg#Stack)


### 簡單例子
在一個陣列中如何找大最大值。
迴圈的思考模式是：從前往後一個一個看，永遠記錄著目前看到的最大值。

m = a[0];
for (i = 1 ; i < n; i++)
    m = max(m, a[i]);

分治思考模式：如果我們把陣列在i的位置分成前後兩段
$a[0,i−1]$ 與 $a[i,n]$，分別求最大值，再返回兩者較大者。切在哪裡呢？如果切在最後一個的位置，因為右邊只剩一個無須遞迴，那麼會是

int find_m1(int n) {
    if (n == 0) return a[0]; 
    return max(find_m1(n - 1), a[n]);
}

這是個尾端遞迴 (Tail Recursion)，在有編譯最佳化的狀況下可跑很快，其實可發現程式的行為就是上面那個迴圈的版本。若我們將程式切在中點:

int find_m2(int left, int right) { // 範圍=[left, right) 慣用左閉右開區間
    if (right - left == 1) return a[left]; 
    int mid = (left + right) / 2 ;
    return max(find_max(left, mid), find_max(midi, right);
}

### 尾端遞迴 (Tail Recursion)

#### Tail Call
Tail Call 概念很簡單，就是在 function 的最後語句執行另一個 function call。

int search(int data)
{
  return advanced_search(data);
}

#### Tail recursion
在尾端再次呼叫自身程式，就被稱為 Tail recursion

#### Tail recursion Optimization
在 Tail recursion Optimization 部分，只需要把處理過後的數值儲存起來，接著跳轉到同一個 function 最前端重複執行即可。反過來看，如果沒有經過優化的話，那麼就需要耗費 stack 空間為相同的 function 建立新的 stack frame。


### Fibonacci Number

#### Recursive

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib (n - 2);
}

digraph hierarchy {
graph [nodesep="1"];

11 [label="Fib(5)" shape=box];
21 [label="Fib(4)" shape=box];
22 [label="Fib(3)" shape=box];
31 [label="Fib(3)" shape=box];
32 [label="Fib(2)" shape=box];
33 [label="Fib(2)" shape=box];
34 [label="Fib(1)=1" shape=box];
41 [label="Fib(2)" shape=box];
42 [label="Fib(1)=1" shape=box];
43 [label="Fib(1)=1" shape=box];
44 [label="Fib(0)=0" shape=box];
45 [label="Fib(1)=1" shape=box];
46 [label="Fib(0)=0" shape=box];
51 [label="Fib(1)=1" shape=box];
52 [label="Fib(0)=0" shape=box];

11 ->{21 22}
21 ->{31 32}
22 ->{33 34}
31 -> {41 42}
32 -> {43 44}
33 -> {45 46}
41 -> {51 52}
}

#### Iterative

int fib(int n) {
    int pre = -1;
    int result = 1;
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum = result + pre;
        pre = result;
        result = sum;
    }
    return result;
}

#### Tail recursion
此法可加速原先之遞迴，可減少一半的資料回傳，而概念上是運用從第一次 call function 後即開始計算值，不像之前的遞迴需 call function 至中止條件後才開始計算值，再依序傳回到最上層，因此可大幅降低時間，減少 stack 使用量。參考實做如下：

int fib(int n, int a, int b) {
    if (n == 0) return a;
    return fib(n - 1 , b, a + b);
}

digraph hierarchy {

nodesep=1.0 // increases the separation between nodes

node [fontname=Courier,shape=box] //All nodes will this shape and colour

"Fib(5,0,1)"->"Fib(4,1,1)"
"Fib(4,1,1)"->"Fib(3,1,2)" 
"Fib(3,1,2)"->"Fib(2,2,3)"
"Fib(2,2,3)"->"Fib(1,3,5)"
"Fib(1,3,5)"->"return 5"
                
}

### 複雜度分析
| 方法 | 複雜度 |
| -------- | -------- |
| Recursive | $O(2^n)$ |
| Iterative | $O(n)$ |
| Tail Recursion | $O(n)$ |
| Q-Matrix | $O(log\ n)$ |
| Fast Doubling | $O(log\ n)$ |

### 相關的題目
- [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)
- [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

### To Iterate is Human, to Recurse, Divine
- 「遞迴（recurse）只應天上有，凡人該當用迴圈（iterate）」
- 遞迴
- pros: 複雜的處理都會變得簡單明瞭。
- cons: 遞迴層層呼叫的過程中不停將資料塞入堆疊又從堆疊取出的手續太耗成本
- e.g. 遍歷資料夾下的所有子資料夾與檔案、迷宮路徑的搜尋
- 迴圈
- pros: 以少數幾個變數就可以控制完整的流程。
- cons: 將遞迴改寫成迴圈往往會失去邏輯的簡潔與結構的優雅。
- 要嘛對電腦好，讓它少算一點，少用點空間
- 要嘛對人好，電腦多做點工
- 遞迴程式沒有你想像中的慢

### 其他
注意: Python 沒有 tail recursion 優化，而且 stack 深度不到 1000。C 要開編譯器開啟最佳化才會做 tail recursion 優化。但是 leetcode C++ 其實有開 `-O2`。

[3.11 Options That Control Optimization](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)
> Enabled at levels -O2, -O3, -Os.

## 指標 Pointer
> 「指標」扮演「記憶體」和「物件」之間的橋樑

### 頭腦體操?
科技公司面試題:

void **(*d) (int &, char **(*)(char *, char **));

上述宣告的解讀：

- d is a pointer to a function that takes two parameters:
- a reference to an int and
- a pointer to a function that takes two parameters:
- a pointer to a char and
- a pointer to a pointer to a char
- and returns a pointer to a pointer to a char
- and returns a pointer to a pointer to void

### 入門
[C語言: 超好懂的指標，初學者請進～](https://kopu.chat/c%e8%aa%9e%e8%a8%80-%e8%b6%85%e5%a5%bd%e6%87%82%e7%9a%84%e6%8c%87%e6%a8%99%ef%bc%8c%e5%88%9d%e5%ad%b8%e8%80%85%e8%ab%8b%e9%80%b2%ef%bd%9e/)


### 規格書
規格書 [ISO/IEC 9899 (簡稱 “C99”)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)和指標相關的描述：

`&` 不要都念成 and，涉及指標操作的時候，要讀為 "address of"
`*` 要讀為 "Indirection (dereference)"

C99 標準 [6.5.3.2] Address and indirection operators 提到 ‘&’ address-of operator

### 英文很重要
安裝 `cdecl` 程式，可以幫你產生 C 程式的宣告。

$ sudo apt-get install cdecl

#### 使用案例一:

$ cdecl
cdecl> declare a as array of pointer to function returning pointer to function returning pointer to char

會得到以下輸出:

char *(*(*a[])())()

解釋

char *(*(*a[])())()

char *() () 
*(*a[])()

typedef char* (*func_t) () -> char* (*)()

func_t *(*a[])()

#### 使用案例二
把前述 C99 規格的描述帶入，可得:

cdecl> declare array of pointer to function returning struct tag

struct tag (*var[])()

如果你沒辦法用英文來解說 C 程式的宣告，通常表示你不理解！

`cdecl` 可解釋 C 程式宣告的意義，比方說：

cdecl> explain char *(*fptab[])(int)
declare fptab as array of pointer to function (int) returning pointer to char

### 沒有「雙指標」只有「指標的指標」
C 語言中，萬物皆是數值 (everything is a value)，函式呼叫當然只有 call-by-value。「指標的指標」(英文就是 a pointer of a pointer) 是個常見用來改變「傳入變數原始數值」的技巧。

int B = 2;
void func(int *p) { p = &B; }
int main() {
    int A = 1, C = 3;
    int *ptrA = &A;
    func(ptrA);
    printf("%d\n", *ptrA);
    return 0;
}

在第 5 行 (含) 之前的記憶體示意:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structptr [label="ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
}

第 6 行 `ptrA` 數值傳入 `func` 後的記憶體示意:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    
    structp [label="p|<p>&A"]
    structptr [label="<name_ptr> ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
    structp:p -> structa:A:nw
    
}

- `func` 依據 [函式呼叫篇](https://hackmd.io/s/HJpiYaZfl) 描述，將變數 `p` 的值指定為 `&B`

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structp [label="p|<p>&B"]
    structptr [label="<name_ptr> ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
    structp:p -> structb:B:nw  
}

由上圖可見，原本在 main 中的 `ptrA` 內含值沒有改變。這不是我們期望的結果，該如何克服呢？可透過「指標的指標」來改寫，如下：

int B = 2;
void func(int **p) { *p = &B; }
int main() {
    int A = 1, C = 3;
    int *ptrA = &A;
    func(&ptrA);
    printf("%d\n", *ptrA);
    return 0;
}

在第 5 行 (含) 之前的記憶體示意:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structptr [label="ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
}

第 6 行時，傳入 `func` 的參數是 `&ptrA`，也就是下圖中的 `&ptrA(temp)`:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structadptr [label="&ptrA(temp)|<adptr> &ptrA"]
    structptr [label="<name_ptr> ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
    structadptr:adptr -> structptr:name_ptr:nw
}

進入 func 執行後，在編譯器產生對應參數傳遞的程式碼中，會複製一份剛傳入的 `&ptrA`，產生一個自動變數 `p`，將 `&ptrA` 內的值存在其中，示意如下:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structp [label="p(in func)|<p> &ptrA"]
    structadptr [label="&ptrA(temp)|<adptr> &ptrA"]
    structptr [label="<name_ptr> ptrA|<ptr> &A"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structa:A:nw
    structadptr:adptr -> structptr:name_ptr:nw
    structp:p -> structptr:name_ptr:nw
}

在 `func` 中把 `p` 指向到的值換成 `&B`:

digraph structs {
	node[shape=record]
    {rank=same; structa,structb,structc}
    structp [label="p(in func)|<p> &ptrA"]
    structadptr [label="&ptrA(temp)|<adptr> &ptrA"]
    structptr [label="<name_ptr> ptrA|<ptr> &B"];
	structb [label="<B> B|2"];
    structa [label="<A> A|1"];
    structc [label="<C> C|3"]; 	
	
    structptr:ptr -> structb:B:nw
    structadptr:adptr -> structptr:name_ptr:nw
    structp:p -> structptr:name_ptr:nw
}

經過上述「指標的指標」，`*ptrA` 的數值從 1 變成 2，而且 `ptrA` 指向的物件也改變了。

### Pointers vs. Arrays

- array vs. pointer
- in declaration
- extern, 如 `extern char x[];` $\to$ 不能變更為 pointer 的形式
- definition/statement, 如 `char x[10]` $\to$ 不能變更為 pointer 的形式
- parameter of function, 如 `func(char x[])` $\to$ 可變更為 pointer 的形式 $\to$ `func(char *x)`
- in expression
- array 與 pointer 可互換

int main() {
    int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%d %d %d %d\n", x[4], *(x + 4), *(4 + x), 4[x]);
}
// 4 4 4 4

:::info
`x[i]` 總是被編譯器改寫為 `*(x + i)` $←$ in expression
:::

### Array subscripting
- C 提供操作多維陣列的機制 (C99 [6.5.2.1] **_Array subscripting_**)，但實際上只有一維陣列的資料存取
- 對應到線性記憶體
- Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n ≥ 2) with dimensions i × j × ... × k, then E (used as other than an lvalue) is converted to a pointer to an (n − 1)-dimensional array with dimensions j × ... × k. If the unary * operator is applied to this pointer explicitly, or implicitly as a result of subscripting, the result is the pointed-to (n − 1)-dimensional array, which itself is converted into a pointer if used as other than an lvalue. It follows from this that arrays are stored in row-major order (last subscript varies fastest)
- Consider the array object defined by the declaration `int x[3][5];` Here x is a 3 × 5 array of ints; more precisely, x is an array of three element objects, each of which is an array of five ints. In the expression `x[i]`, which is equivalent to `(*((x)+(i)))`, x is first converted to a pointer to the initial array of five ints. Then i is adjusted according to the type of x, which conceptually entails multiplying i by the size of the object to which the pointer points, namely an array of five int objects. The results are added and indirection is applied to yield an array of five ints. **When used in the expression `x[i][j]`, that array is in turn converted to a pointer to the first of the ints, so `x[i][j]` yields an int.**
- array subscripting 在**編譯時期**只確認以下兩件事:
- 得知 size
- 取得陣列第 0 個 (即最初的一項) 元素的指標
- 前兩者以外的操作，都透過 pointer
- array subscripting => syntax sugar
- Array declaration:

int a[3];
struct { double v[3]; double length; } b[17];
int calendar[12][31];

那麼...

sizeof(calendar) = ? sizeof(b) = ?

善用 GDB，能省下沒必要的 `printf()`，並可互動分析: (下方以 GNU/Linux x86_64 作為示範平台)

- 有時會遇到程式邏輯和結果正確，但因為 `printf()` 的輸出格式沒用對，而誤以為自己程式沒寫好的狀況

(gdb) p sizeof(calendar)
$1 = 1488
(gdb) print 1488 / 12 / 31
$2 = 4
(gdb) p sizeof(b)
$3 = 544

### Lvalue 的作用
有兩個詞彙常令人誤解: `lvalue` (C 和 C++ 都有) 和 `rvalue` (C++ 特有) —— 兩者都是對運算式（expression）的分類方式。

CPL 開始對運算式區分為左側模式 (left-hand mode) 與右側模式 (right-hand mode)，左、右是指運算式是在指定的左或右側，有些運算式只有在指定的左側才會有意義。C 語言有類似的分類方式，分為 `lvalue` 與其他運算式，似乎 `l` 暗示著 left 的首字母，不過 C 語言標準中明確聲明 `l` 是 "locator" (定位器) 的意思，lvalue 定義為 "locator value"，亦即 lvalue 是個物件的表示式 (an expression referring to an object)，該物件的型態可以是一般的 object type 或 incomplete type，但不可為 `void`。換句話說，運算式的結果會是個有名稱的物件。

到了 C++ 98，非 lvalue 運算式被稱為 `rvalue`，而部分在 C 語言隸屬「非 lvalue 的運算式」變成 lvalue，後續在 C++ 11，運算式又被重新分類為 lvalue, prvalue, xvalue, lvalue 與 rvalue。

某些文件將 lvalue 和 rvalue 分別譯為左值、右值，這種翻譯方式顯然過時，且偏離 C 和 C++ 語言規格的定義，我們要知道，lvalue 和 rvalue 只是個分類名稱。

在規格書的 Rationale 將 lvalue 定義為 object locator (C99)
* C99 6.3.2.1 footnote
> The name "lvalue" comes originally from the `assignment expression` E1 = E2, in which the left operand E1 is required to be a (modifiable) lvalue. It is perhaps better considered as representing an object `"locator value"`. What is sometimes called "rvalue" is in this International Standard described as the `"value of an expression"`. An obvious example of an lvalue is an identifier of an object. As a further example, if E is a unary expression that is a pointer to an object, *E is an lvalue that designates the object to which E points.

舉例來說：

int a = 10;
int *E = &a;
++(*E);  // a = a + 1
++(a++); // error

E 就是上面 C99 註腳提及的 "a pointer to an object" (這裡的 object 指的就是 a 佔用的記憶體空間)，下面列舉 E 這個 identifier 不同角度所代表的身份：
* `E`
+ object: 儲存 address of int object 的區域
+ lvalue: E object 的位置，也就是 E object 這塊區域的 address
* `*E`
+ lvalue: 對 E 這個 object 做 **dereference** 也就是把 E object 所代表的內容 (address of int object) 做 dereference，也就得到了 int object 的位置，換個說法就是上面所提到的 lvalue that designates the object which E points

以 gcc 編譯上方程式碼會產生
> error: **lvalue** required as increment operand

錯誤訊息，因為 `a++` 會回傳 a 的 value，而這個 value 是暫存值也就是個 non-lvalue。
而 `++()` 這個 operator 的 operand 必須要是一個 lvalue，因為要寫回 data，需要有地方 (location) 可寫入
* 延伸閱讀: [Understanding lvalues and rvalues in C and C++](http://eli.thegreenplace.net/2011/12/15/understanding-lvalues-and-rvalues-in-c-and-c)

## linked list
### 從 Linux 核心的藝術談起

[Linus Torvalds 在 TED 2016 的訪談](http://www.ted.com/talks/linus_torvalds_the_mind_behind_linux?language=zh-tw)

> 「我不是願景家，我是工程師。我對那些四處遊蕩、望著雲端的人沒有任何意見。但是我是看著地面的人，我想修補就在我面前的坑洞，以免跌進去。」

Linus Torvalds 在 TED 訪談中提及自己的思維模式、性格與 Linux 和 Git 背後的心路歷程。

於 [14:10](https://youtu.be/o8NPllzkFhE?t=850) 時，他提到程式設計的 "good taste" 為何。

:::info
對照 CMU 教材 ==[Linked Lists](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/linked%20lists.html)==
* 3 exceptional cases, we need to take care of:
- list is empty
- delete the head node
- node is not in the list

以下的討論不涵蓋 list is empty 和 node is not in the list 的狀況
:::

- [ ] 原本的程式碼 (10 行)

void remove_list_node(List *list, Node *target)
{
    Node *prev = NULL;
    Node *current = list->head;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

直觀的寫法會有特例，也就是第一筆資料與中間的資料的移去操作不同。

若要移去的是第一筆資料，那就需要把指標指向第一個節點；而若是要移除中間的資料，則須要把指標指向目標的前一個節點。

- [ ] 有「品味」的版本 (4 行)

void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

Linus Torvalds 換個角度來思考，通過指標的指標來操作，如此一來，上面的特例就不存在。

Linus Torvalds 的解說:
> People who understand pointers just use a "pointer to the entry pointer", and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing`*pp = entry->next`.

在 [15:25](https://youtu.be/o8NPllzkFhE?t=925) 時，他說:
> It does not have the if statement. And it doesn't really matter -- I don't want you understand why it doesn't have the if statement, but I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case. And that's good code. But this is simple code. This is CS 101. This is not important -- although, details are important.

重點是有時候我們可以從不同的角度來詮釋問題，然後重寫，那麼例外就會消失，這樣就是好的程式。

原本的方式是，有個指向前一元素的指標、另一個目前位置的指標，再利用 `while` 敘述逐一走訪鏈結串列，找到 `target` 時停下來。這會有個分支判斷 `prev` 是否為 `NULL`，若為 `NULL` 就代表 target 是鏈結串列的 head，因此需要把鏈結串列的 head 指向下個元節點；若非 `NULL` 就把前個節點的 `next` 設為目前的下一個節點。


而 Linus Torvalds 的想法則是拿一個指標指向「節點裡頭指向下個節點 的指標」，以「要更新的位址」為思考點來操作。

有個指標的指標 `indirect`，一開始指向 head，之後一樣走訪 list，解指標看是不是我們要的 target，如果 `*indirect` 就是我們要移去的元素，代表 `indirect` 現在指向前一個節點裡面的 `next` 指標，因此把 `*indirect` 設為 target 的下個節點，即可完成整個操作：

> 圖解出處: [The mind behind Linux 筆記](https://hackmd.io/@Mes/The_mind_behind_Linux)

解說: [Linked lists, pointer tricks and good taste](https://github.com/mkirchner/linked-list-good-taste)

> [符合 Linux 核心風格的調整](https://github.com/felipec/linked-list-good-taste)

### 案例探討: [LeetCode 21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
直觀的做法是，提供一個暫時節點，依序將內含值較小的節點串上，最後回傳暫時節點指向的次個節點:

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    struct ListNode *ptr = head;
    while (L1 && L2) {
        if (L1->val < L2->val) {
            ptr->next = L1;
            L1 = L1->next;
        } else {
            ptr->next = L2;
            L2 = L2->next;
        }
        ptr = ptr->next;
    }
    ptr->next = L1 ? L1 : L2;
    return head->next;
}

倘若我們想避免配置暫時節點的空間 (即上方程式碼中的 `malloc`)，該怎麼做？運用上述 indirect pointer 的技巧:

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2) { 
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

觀察使用 indirect pointer 版本的程式碼，其中 `if-else` 的程式碼都是將 ptr 指向下一個要接上的節點，之後將節點更新到下一個，不過要為 L1 跟 L2 分開寫同樣的程式碼，該如何簡化？可以再使用一個指標的指標來指向 L1 或 L2。

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

## 問題
- Two sum
- sorting: Time nlogn 才對
- [0100. Same Tree](https://hackmd.io/n-YP_YoESXukygDaORdtkw)
- 題目理解，好像沒問題了?
- Preorder/Inorder/Postorder/Levelorder？？？
- 複雜度分析
- [0110. Balanced Binary Tree](https://hackmd.io/mDgn56uLR660Dlyv6JjAlA)
- 看完題目想了也不知道怎麼做，引導想法 直覺想法
- 再寫一次
- Recursion top-down bottom-up 複雜度分析
- [0021. Merge Two Sorted Lists](https://hackmd.io/wvMTTCMMR7KhO0ROm1EdFQ)
- `.` member access
- `->` member access through pointer
- 複雜度分析