單鏈表反轉(zhuǎn)是面試中??嫉囊坏李},這道題看起來(lái)簡(jiǎn)單,但是能一遍寫出 bug free 的代碼相當(dāng)不容易,本文主要提供遞歸和迭代兩種解題方法,供大家參考。 題目
舉栗為了便于理解,以 1->2->3->NULL 為栗子,如下圖示:
遞歸解法鏈表具有天然的遞歸性,一個(gè)鏈表例如:1->2->3->NULL,可以看成以值為 1 的節(jié)點(diǎn)作為頭節(jié)點(diǎn)后面掛接一個(gè)更短的(以值為 2 的節(jié)點(diǎn)為頭節(jié)點(diǎn))的鏈表,即1->更短的鏈表(以值為2的節(jié)點(diǎn)作為頭節(jié)點(diǎn)),同理以值為2的節(jié)點(diǎn)作為頭節(jié)點(diǎn)后面也掛接一個(gè)更更短的鏈表(以值為3的節(jié)點(diǎn)作為頭節(jié)點(diǎn));依次類推,如下圖示。
有了這樣的思考,鏈表反轉(zhuǎn)就可以先翻轉(zhuǎn)頭節(jié)點(diǎn)后面掛接的更短的鏈表,然后再在翻轉(zhuǎn)后的更短鏈表的后面掛接之前的頭節(jié)點(diǎn)。具體如下圖示:
Show me the Code// C語(yǔ)言版本 struct ListNode* reverseList(struct ListNode* head){ /* 特判 */ if (head == NULL || head->next == NULL) { return head; } /* 翻轉(zhuǎn)頭節(jié)點(diǎn)(節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)) 后面掛接的鏈表(以節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)作為頭節(jié)點(diǎn)) */ /* 翻轉(zhuǎn)之后變成 3->2 */ struct ListNode *node = reverseList(head->next); /* 將頭節(jié)點(diǎn)(節(jié)點(diǎn)值為 1 的節(jié)點(diǎn))掛接在翻轉(zhuǎn)之后的鏈表的后面(也就是節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)的后面) */ head->next->next = head; /* 將尾節(jié)點(diǎn)的下一節(jié)點(diǎn)置空 */ 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; 迭代(雙指針)解法可以用雙指針來(lái)做,用一個(gè)指針 next 記錄當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn),另外一個(gè)指針 pre 記錄當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn),如果當(dāng)前節(jié)點(diǎn)是頭節(jié)點(diǎn),則 pre 為空指針,還是以鏈表:1->2->3->NULL 為栗子,具體如下圖示。
Show me the Code// C語(yǔ)言版本 struct ListNode* reverseList(struct ListNode* head){ /* 記錄當(dāng)前節(jié)點(diǎn)的前一節(jié)點(diǎn) */ struct ListNode* pre = NULL; while (head != NULL) { /* 記錄當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn) */ struct ListNode* next = head->next; head->next = pre; pre = head; head = next; } return pre; }
// go語(yǔ)言版本 func reverseList(head *ListNode) *ListNode { var pre *ListNode = nil for head != nil { next := head.Next head.Next = pre; pre = head head = next } return pre } |
|