成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 206：反轉(zhuǎn)鏈表 Reverse Linked List

Gilbertat / 3520人閱讀

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

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

Reverse a singly linked list.

示例:

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

進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

Follow up:

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

解題思路：

每次遍歷到最后一位取節(jié)點(diǎn)這種方法就算了時(shí)間復(fù)雜度太高。如題目進(jìn)階要求的兩種方法，迭代和遞歸：

迭代：

每次分出來一個節(jié)點(diǎn)把節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表上：

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

分離第一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表：1 原鏈表：2->3->4->5

分離下一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表：2->1 原鏈表：3->4->5

分離下一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表：3->2->1 原鏈表：4->5

分離下一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表：4->3->2->1 原鏈表：5

分離下一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)添加到新鏈表：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暫存當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
            head.next = pre;//當(dāng)前節(jié)點(diǎn)下一個指向pre
            pre = head;//刷新pre
            head = tmp;//刷新當(dāng)前節(jié)點(diǎn)為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
遞歸：

其實(shí)就是用遞歸完成棧的功能：先進(jìn)后出

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

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

遞歸到最后一層時(shí)遇到null節(jié)點(diǎn)返回尾節(jié)點(diǎn)5

回到上一層遞歸 分離節(jié)點(diǎn) 5 作為新鏈表的尾節(jié)點(diǎn)：5，置空原本5節(jié)點(diǎn)，原鏈表1->2->3->4->null

回到上一層遞歸 分離節(jié)點(diǎn) 4 作為新鏈表的尾節(jié)點(diǎn)：5->4，置空原本4節(jié)點(diǎn)，原鏈表1->2->3->null

回到上一層遞歸 分離節(jié)點(diǎn) 3 作為新鏈表的尾節(jié)點(diǎn)：5->4->3，置空原本3節(jié)點(diǎn)，原鏈表1->2->null

回到上一層遞歸 分離節(jié)點(diǎn) 2 作為新鏈表的尾節(jié)點(diǎn)：5->4->3->2，置空原本2節(jié)點(diǎn)，原鏈表1->null

回到上一層遞歸 分離節(jié)點(diǎn) 1 作為新鏈表的尾節(jié)點(diǎn)：5->4->3->2->1，置空原本1節(jié)點(diǎn)，原鏈表null

Java：

class Solution {
    public ListNode reverseList(ListNode head) {
        //基線條件
        if (head == null || head.next == null) return head;
        //遞歸
        ListNode tmp = head.next;//暫存頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)
        ListNode pre = reverseList(head.next);//遞歸調(diào)用該函數(shù)，pre為返回的新鏈表的頭節(jié)點(diǎn)，原鏈表的最后一個節(jié)點(diǎn)，無論遞歸多少層該返回值一直傳遞不變
        tmp.next = head;//暫存的下一個節(jié)點(diǎn)指向傳入節(jié)點(diǎn)
        head.next = null;//下一個節(jié)點(diǎn)即原本指向tmp的節(jié)點(diǎn) 置空
        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

歡迎關(guān)注公.眾號一起刷題：愛寫B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75516.html

相關(guān)文章

  • LeetCode 之 JavaScript 解答第206題 —— 反轉(zhuǎn)鏈表（Reverse Link

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

    zhangfaliang 評論0 收藏0

  • LeetCode 206：反轉(zhuǎn)鏈表 Reverse Linked List

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

    heartFollower 評論0 收藏0

  • LeetCode 234：回文鏈表 Palindrome Linked List

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

    luqiuwen 評論0 收藏0

  • LeetCode 234：回文鏈表 Palindrome Linked List

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

    hlcc 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

    tain335 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<