單鏈表反轉是面試中常考的一道題，這道題看起來簡單，但是能一遍寫出 bug free 的代碼相當不容易，本文主要提供遞回和迭代兩種解題方法，供大家參考，
題目
舉栗
為了便于理解，以 1->2->3->NULL 為栗子，如下圖示：
遞回解法
鏈表具有天然的遞回性，一個鏈表例如：1->2->3->NULL，可以看成以值為 1 的節點作為頭節點后面掛接一個更短的(以值為 2 的節點為頭節點)的鏈表，即1->更短的鏈表（以值為2的節點作為頭節點），同理以值為2的節點作為頭節點后面也掛接一個更更短的鏈表（以值為3的節點作為頭節點）；依次類推，如下圖示，
有了這樣的思考，鏈表反轉就可以先翻轉頭節點后面掛接的更短的鏈表，然后再在翻轉后的更短鏈表的后面掛接之前的頭節點，具體如下圖示：
Show me the Code
// C語言版本
struct ListNode* reverseList(struct ListNode* head){
/* 特判 */
if (head == NULL || head->next == NULL) {
return head;
}
/* 翻轉頭節點(節點值為 1 的節點) 后面掛接的鏈表(以節點值為 2 的節點作為頭節點) */
/* 翻轉之后變成 3->2 */
struct ListNode *node = reverseList(head->next);
/* 將頭節點(節點值為 1 的節點)掛接在翻轉之后的鏈表的后面(也就是節點值為 2 的節點的后面) */
head->next->next = head;
/* 將尾節點的下一節點置空 */
head->next = NULL;
return node;
}
#python3 版本
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
node = self.reverseList(head.next)
head.next.next = head;
head.next = None;
return node;
迭代（雙指標）解法
可以用雙指標來做，用一個指標 next 記錄當前節點的后一節點，另外一個指標 pre 記錄當前節點的前一個節點，如果當前節點是頭節點，則 pre 為空指標，還是以鏈表：1->2->3->NULL 為栗子，具體如下圖示，
Show me the Code
// C語言版本
struct ListNode* reverseList(struct ListNode* head){
/* 記錄當前節點的前一節點 */
struct ListNode* pre = NULL;
while (head != NULL) {
/* 記錄當前節點的后一節點 */
struct ListNode* next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
// go語言版本
func reverseList(head *ListNode) *ListNode {
var pre *ListNode = nil
for head != nil {
next := head.Next
head.Next = pre;
pre = head
head = next
}
return pre
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260508.html
標籤：其他
上一篇：春節假期的復盤