【面試算法】鏈表反轉

adam1q84 發布于2019-08-14 15:19 / 2182人閱讀

摘要：今天來將一下面試中經常問到的一個問題鏈表反轉。題目給一個單向鏈表，請編寫一個函數，把鏈表反轉，并把反轉的鏈表返回。假設給的節點為雙向鏈表反轉函數如下

今天來將一下面試中經常問到的一個問題：鏈表反轉。

【題目1】給一個單向鏈表，請編寫一個函數，把鏈表反轉，并把反轉的鏈表返回。

假設給的節點為

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}

單向鏈表反轉函數如下

public ListNode reverse1(ListNode head){
    ListNode prev = null;
    while(head != null){
        ListNode next = head.next; //獲取下一個節點
        prev.next = head;          //更改上一個節點的指向  
        prev = head;               //上一個節點前進一位
        head = next;               //head節點前進一位
    }
    return prev;
}

【題目2】給一個雙向鏈表，請編寫一個函數，把鏈表反轉，并把反轉的鏈表返回。
假設給的節點為

class ListNode{
    int val;
    ListNode prev;
    ListNode next;
    public ListNode(int val){
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

雙向鏈表反轉函數如下

public ListNode reverse2(ListNode head){
    ListNode cur = null;
    while(head != null){
        cur = head;
        head = head.next;
        cur.next = cur.prev;
        cur.prev = head;
    }
    return cur;
}

GPU云服務器云服務器 python反轉鏈表鏈表算法鏈表排序算法算法 c語言鏈表

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

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

Java數據結構與算法——鏈表（面試）

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。指針反轉實現鏈表反轉代碼反轉鏈表獲取當前下下個元素測試代碼部分用到了上篇文章數據結構與算法鏈表的代碼段，請移步獲取。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文是上篇文章Java數據結構與算法——鏈表的擴展篇，介紹鏈表的特點，使用場景、鏈表的性能分析以...

keke 2019-08-16 11:08 評論0 收藏0
＜LeetCode天梯＞Day026 反轉鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...

imingyu 2021-11-17 09:33 評論0 收藏0
劍指offer系列——劍指 Offer 24. 反轉鏈表（C語言）

摘要：假設反轉對象節點為，反轉指向的結點為，反轉后指向的結點為首結點。當然也可以根據棧先進后出的特點，使用棧反轉鏈表。 ??前面的話?? 大家好！博主開辟了一個新的專欄—...

weakish 2021-09-03 10:29 評論0 收藏0
反轉鏈表

摘要：扯淡之前聽說過面試反轉鏈表的梗，也嘗試著自己實現了一次，算是比較簡單的問題。當然，前提是我們只持有頭節點的引用，且稱為，那么鏈表反轉后的頭節點，就是。扯淡之前聽說過google面試反轉鏈表的梗，也嘗試著自己實現了一次，算是比較簡單的問題。但在紙上手寫代碼的時候，思維就很亂，可能是隔的時間長忘記了，或者之前就跟本沒有理清思路，所以被虐的很慘。這篇文章的目的就是梳理一下思路，加深印象。...

20171112 2019-08-14 15:16 評論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