LeetCode 206：反轉鏈表 Reverse Linked List

Gilbertat 發布于2019-08-16 18:39 / 3518人閱讀

摘要：反轉一個單鏈表。示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節點這種方法就算了時間復雜度太高。從鏈表末尾向頭部逐個分離節點，并將節點添加到新鏈表的末尾。與迭代法原理相似。

反轉一個單鏈表。

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

遞歸：

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

基線條件為遇到空節點（到鏈表末尾），返回對象為鏈表的最后一個節點，在遞歸函數中傳遞一直不變。從鏈表末尾向頭部逐個分離節點，并將節點添加到新鏈表的末尾。與迭代法原理相似。

原鏈表：1->2->3->4->5

遞歸到最后一層時遇到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

Java：

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;
    }
}

Python3：

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

云服務器 GPU云服務器 python反轉鏈表 linked 服務器206 Reverse

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75516.html

LeetCode 之 JavaScript 解答第206題 —— 反轉鏈表（Reverse Link

摘要：算法思路兩種方法一般反轉遞歸法一般解決定義三個指針，分別為，存儲當前結點，指向反轉好的結點的頭結點，存儲下一結點信息。遞歸法重點分析先確定終止條件當下一結點為時，返回當前節點判斷當前的鏈表是否為遞歸找到尾結點，將其存儲為頭結點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿題目：Reverse...

zhangfaliang 2019-08-23 17:12 評論0 收藏0
LeetCode 206：反轉鏈表 Reverse Linked List

摘要：反轉一個單鏈表。示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節點這種方法就算了時間復雜度太高。從鏈表末尾向頭部逐個分離節點，并將節點添加到新鏈表的末尾。與迭代法原理相似。反轉一個單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...

heartFollower 2019-07-31 11:29 評論0 收藏0
LeetCode 234：回文鏈表 Palindrome Linked List

摘要：請判斷一個鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔心。然后從原鏈表頭節點與反轉后后半部分鏈表頭節點開始對比值即可。 ?請判斷一個鏈表是否為回文鏈表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 輸入: 1->...

luqiuwen 2019-08-16 18:41 評論0 收藏0
LeetCode 234：回文鏈表 Palindrome Linked List

摘要：請判斷一個鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔心。然后從原鏈表頭節點與反轉后后半部分鏈表頭節點開始對比值即可。 ?請判斷一個鏈表是否為回文鏈表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 輸入: 1->...

hlcc 2019-07-31 11:30 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0