【面試算法】鏈表反轉(zhuǎn)

adam1q84 發(fā)布于2019-08-14 15:19 / 2192人閱讀

摘要：今天來(lái)將一下面試中經(jīng)常問(wèn)到的一個(gè)問(wèn)題鏈表反轉(zhuǎn)。題目給一個(gè)單向鏈表，請(qǐng)編寫(xiě)一個(gè)函數(shù)，把鏈表反轉(zhuǎn)，并把反轉(zhuǎn)的鏈表返回。假設(shè)給的節(jié)點(diǎn)為雙向鏈表反轉(zhuǎn)函數(shù)如下

今天來(lái)將一下面試中經(jīng)常問(wèn)到的一個(gè)問(wèn)題：鏈表反轉(zhuǎn)。

【題目1】給一個(gè)單向鏈表，請(qǐng)編寫(xiě)一個(gè)函數(shù)，把鏈表反轉(zhuǎn)，并把反轉(zhuǎn)的鏈表返回。

假設(shè)給的節(jié)點(diǎn)為

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

單向鏈表反轉(zhuǎn)函數(shù)如下

public ListNode reverse1(ListNode head){
    ListNode prev = null;
    while(head != null){
        ListNode next = head.next; //獲取下一個(gè)節(jié)點(diǎn)
        prev.next = head;          //更改上一個(gè)節(jié)點(diǎn)的指向  
        prev = head;               //上一個(gè)節(jié)點(diǎn)前進(jìn)一位
        head = next;               //head節(jié)點(diǎn)前進(jìn)一位
    }
    return prev;
}

【題目2】給一個(gè)雙向鏈表，請(qǐng)編寫(xiě)一個(gè)函數(shù)，把鏈表反轉(zhuǎn)，并把反轉(zhuǎn)的鏈表返回。
假設(shè)給的節(jié)點(diǎn)為

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

雙向鏈表反轉(zhuǎn)函數(shù)如下

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云服務(wù)器云服務(wù)器 python反轉(zhuǎn)鏈表鏈表算法鏈表排序算法算法 c語(yǔ)言鏈表

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

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

相關(guān)文章

Java數(shù)據(jù)結(jié)構(gòu)與算法——鏈表（面試）

摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專(zhuān)題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。指針?lè)崔D(zhuǎn)實(shí)現(xiàn)鏈表反轉(zhuǎn)代碼反轉(zhuǎn)鏈表獲取當(dāng)前下下個(gè)元素測(cè)試代碼部分用到了上篇文章數(shù)據(jù)結(jié)構(gòu)與算法鏈表的代碼段，請(qǐng)移步獲取。聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專(zhuān)題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文是上篇文章Java數(shù)據(jù)結(jié)構(gòu)與算法——鏈表的擴(kuò)展篇，介紹鏈表的特點(diǎn)，使用場(chǎng)景、鏈表的性能分析以...

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

摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車(chē)神哥，府學(xué)路18號(hào)的車(chē)神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...

imingyu 2021-11-17 09:33 評(píng)論0 收藏0
劍指offer系列——?jiǎng)χ?Offer 24. 反轉(zhuǎn)鏈表（C語(yǔ)言）

摘要：假設(shè)反轉(zhuǎn)對(duì)象節(jié)點(diǎn)為，反轉(zhuǎn)指向的結(jié)點(diǎn)為，反轉(zhuǎn)后指向的結(jié)點(diǎn)為首結(jié)點(diǎn)。當(dāng)然也可以根據(jù)棧先進(jìn)后出的特點(diǎn)，使用棧反轉(zhuǎn)鏈表。 ??前面的話(huà)?? 大家好！博主開(kāi)辟了一個(gè)新的專(zhuān)欄—...

weakish 2021-09-03 10:29 評(píng)論0 收藏0
反轉(zhuǎn)鏈表

摘要：扯淡之前聽(tīng)說(shuō)過(guò)面試反轉(zhuǎn)鏈表的梗，也嘗試著自己實(shí)現(xiàn)了一次，算是比較簡(jiǎn)單的問(wèn)題。當(dāng)然，前提是我們只持有頭節(jié)點(diǎn)的引用，且稱(chēng)為，那么鏈表反轉(zhuǎn)后的頭節(jié)點(diǎn)，就是。扯淡之前聽(tīng)說(shuō)過(guò)google面試反轉(zhuǎn)鏈表的梗，也嘗試著自己實(shí)現(xiàn)了一次，算是比較簡(jiǎn)單的問(wèn)題。但在紙上手寫(xiě)代碼的時(shí)候，思維就很亂，可能是隔的時(shí)間長(zhǎng)忘記了，或者之前就跟本沒(méi)有理清思路，所以被虐的很慘。這篇文章的目的就是梳理一下思路，加深印象。...

20171112 2019-08-14 15:16 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(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 題。一目錄不折騰的前端，和咸魚(yú)有什么區(qū)別...

tain335 2019-08-26 10:28 評(píng)論0 收藏0