「算法」鏈表的翻轉

問題

定義一個方法（函數），實現輸入一個鏈表的頭結點，然後可以反轉這個鏈表的方向，並輸出反轉之後的鏈表的頭結點

解決方案

鏈表的翻轉常見的解決方法為遞歸和非迭代法

一、迭代法

迭代的方式是從鏈頭結點開始處理，如下圖

首先對鏈表設置兩個指針NewH,P

我們需要一個臨時結點tmp保存要迭代的結點，防止找不到下一個結點。 在把當前結點指向新結點NewH(p->next=newH)，然後讓新結點前進(newH=p), P指針繼續向後移動，直到P指針指向NULL停止迭代.

最後一步

代碼示例：

typedef struct Node {
 int data;
 struct Node *next;
} Node, List;
List *reverseList(List *Head) {
 if (Head == NULL || Head->next == NULL)
 return Head;
 Node *p = Head;
 Node *newH = NULL;
 while (p->next != NULL) { //一直迭代到鏈尾
 Node *tmp = p->next; //暫存p下一個地址，防止變化指針指向後找不到後續的數
 p->next = newH; //p.next指向前一個空間
 newH = p; //新鏈表的頭移動p, 擴長一步鏈表
 p = tmp; //p指向原始鏈表p指向的下一個空間
 }
 return newH;
}

二、遞歸

迭代是從前向後開始依次反轉，遞歸則是先循環到最後一個元素，從後開始反轉。

直接上代碼

typedef struct Node {
 int data;
 struct Node *next;
} Node, List;
List *reverseList(List *p) {
 if (p == NULL || p->next == NULL) {
 return p; //鏈表為空直接返回，而p->next為空是遞歸基
 }
 Node *newH = reverseList(p->next); //一直循環到鏈尾
 p->next->next = p; //翻轉鏈表的指向
 p->next = null; //記得賦值NULL，防止鏈表錯亂
 return newH; //新鏈表頭永遠指向的是原鏈表的鏈尾
}

參考

[鏈表的翻轉](https://www.jianshu.com/p/125ca1a2ac22)