LeetCode 206：反轉連結清單 Reverse Linked List

反轉一個單連結清單。

Reverse a singly linked list.

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL           

進階:

你可以疊代或遞歸地反轉連結清單。你能否用兩種方法解決這道題？

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解題思路：

每次周遊到最後一位取節點這種方法就算了時間複雜度太高。如題目進階要求的兩種方法，疊代和遞歸：

疊代：

每次分出來一個節點把節點作為頭節點添加到新連結清單上：

原連結清單：1->2->3->4->5

分離第一個節點作為頭節點添加到新連結清單：1 原連結清單：2->3->4->5

分離下一個節點作為頭節點添加到新連結清單：2->1 原連結清單：3->4->5

分離下一個節點作為頭節點添加到新連結清單：3->2->1 原連結清單：4->5

分離下一個節點作為頭節點添加到新連結清單：4->3->2->1 原連結清單：5

分離下一個節點作為頭節點添加到新連結清單：5->4->3->2->1 原連結清單：null

Java：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode tmp = null;
        while (head != null) {
            tmp = head.next;//tmp暫存目前節點的下一個節點
            head.next = pre;//目前節點下一個指向pre
            pre = head;//重新整理pre
            head = tmp;//重新整理目前節點為tmp
        }
        return pre;
    }
}           

Python3：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre,tmp=None,None
        while(head):
            tmp=head.next
            head.next=pre
            pre=head
            head=tmp
        return pre           

遞歸：

其實就是用遞歸完成棧的功能：先進後出

基線條件為遇到空節點（到連結清單末尾），傳回對象為連結清單的最後一個節點，在遞歸函數中傳遞一直不變。從連結清單末尾向頭部逐個分離節點，并将節點添加到新連結清單的末尾。與疊代法原理相似。

遞歸到最後一層時遇到null節點傳回尾節點5

回到上一層遞歸 分離節點 5 作為新連結清單的尾節點：5，置空原本5節點，原連結清單1->2->3->4->null

回到上一層遞歸 分離節點 4 作為新連結清單的尾節點：5->4，置空原本4節點，原連結清單1->2->3->null

回到上一層遞歸 分離節點 3 作為新連結清單的尾節點：5->4->3，置空原本3節點，原連結清單1->2->null

回到上一層遞歸 分離節點 2 作為新連結清單的尾節點：5->4->3->2，置空原本2節點，原連結清單1->null

回到上一層遞歸 分離節點 1 作為新連結清單的尾節點：5->4->3->2->1，置空原本1節點，原連結清單null

class Solution {
    public ListNode reverseList(ListNode head) {
        //基線條件
        if (head == null || head.next == null) return head;
        //遞歸
        ListNode tmp = head.next;//暫存頭節點的下一個節點
        ListNode pre = reverseList(head.next);//遞歸調用該函數，pre為傳回的新連結清單的頭節點，原連結清單的最後一個節點，無論遞歸多少層該傳回值一直傳遞不變
        tmp.next = head;//暫存的下一個節點指向傳入節點
        head.next = null;//下一個節點即原本指向tmp的節點 置空
        return pre;
    }
}           

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tmp = head.next
        pre = self.reverseList(head.next)
        tmp.next = head
        head.next = None
        return pre           

歡迎關注公.衆号一起刷題：愛寫Bug