題目

反轉(zhuǎn)一個(gè)單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

方法一 迭代法

思路

1. 創(chuàng)建一個(gè)新的頭節(jié)點(diǎn) new_head
2. 在整個(gè)遍歷的過程中，一共涉及到三個(gè)節(jié)點(diǎn)，新的頭節(jié)點(diǎn)，原鏈表中的頭節(jié)點(diǎn)以及頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
3. 首先要將頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)保存起來，這樣在原頭節(jié)點(diǎn)反轉(zhuǎn)到新頭節(jié)點(diǎn)的時(shí)候，不會(huì)使鏈表斷掉
4. 然后，進(jìn)行反轉(zhuǎn)，將原頭節(jié)點(diǎn)的next指向新頭節(jié)點(diǎn)
5. 最后，移動(dòng)指針，再重復(fù)上述操作，即遍歷鏈表
6. 時(shí)間復(fù)雜度：O(n)
   空間復(fù)雜度：O(1)

代碼

class Solution(object):
    def reverseList(self, root):
        new_head = None
        head = root
        while head:
            nxt = head.next
            head.next = new_head
            new_head = head
            head = nxt
        return new_head

方法二 遞歸

思路

1. 這種方法相當(dāng)于從后往前遍歷
2. 讓新舊頭節(jié)點(diǎn)先移動(dòng)在鏈表的最后，然后反轉(zhuǎn)鏈表

代碼

    def reverseList(self, head):
        if  head== None or head.next == None:
            return head
        root = self.reverseList(head.next) # 將頭節(jié)點(diǎn)移動(dòng)到最后，然后從后往前遍歷
        head.next.next = head  # 反轉(zhuǎn)鏈表
        head.next = None  # 打破原鏈表中當(dāng)前節(jié)點(diǎn)與下一個(gè)的關(guān)系， 使其變成相當(dāng)于鏈表中的最后一個(gè)節(jié)點(diǎn)，可以看做初始化。
        return root

參考： https://blog.csdn.net/FX677588/article/details/72357389