刷題6 劍指 Offer — 鏈表

劍指 Offer 18. 刪除鏈表的節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz4mp2/
時間復(fù)雜度:O(n)租谈,空間復(fù)雜度:O(1)

var deleteNode = function(head, val) {
    if(head == null){
        return null;
    }
    if(head.val == val){
        return head.next;
    }
    var left = head;
    var cur = left.next
    while(cur.val != val && cur.next!= null){
        left=cur;
        cur=cur.next;
    }
    if(cur != null){
        left.next=cur.next
    }
    return head
};

劍指 Offer 22. 鏈表中倒數(shù)第 k 個節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzy5ei/
時間復(fù)雜度:O(n)椅挣,空間復(fù)雜度:O(1)

var getKthFromEnd = function(head, k) {
    var cur = head;
    var post= head;
    for(var i=0; i<k; i++){
        cur = cur.next;
    }
    while(cur!=null){
        cur = cur.next;
        post = post.next
    }
    return post
};

劍指 Offer 24. 反轉(zhuǎn)鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzccxg/
時間復(fù)雜度:O(n)侥猬,空間復(fù)雜度:O(1)

var reverseList = function(head) {
    var cur = null;
    var pre = head;
    while(pre!=null){
       var tmp = pre.next;
        pre.next = cur;
        cur = pre;
        pre = tmp;
    }
    return cur
};

劍指 Offer 25. 合并兩個排序的鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzjkjj/
輸入兩個遞增排序的鏈表榨了,合并這兩個鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的识颊。O(m+n)

var mergeTwoLists = function(l1, l2) {
    if(l2==null){
        return l1
  }
    if(l1==null){
        return l2
  }
    if(l1.val>l2.val){
        l2.next = mergeTwoLists(l1,l2.next);
        return l2
    }else{
        l1.next = mergeTwoLists(l2,l1.next);
        return l1
    }
};

劍指 Offer 52. 兩個鏈表的第一個公共節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xshucr/
使用兩個指針 node1杂拨,node2 分別指向兩個鏈表 headA锡凝,headB 的頭結(jié)點(diǎn)杉女,然后同時分別逐結(jié)點(diǎn)遍歷贰剥,
當(dāng) node1 到達(dá)鏈表 headA 的末尾時头谜,重新定位到鏈表 headB 的頭結(jié)點(diǎn);
當(dāng) node2 到達(dá)鏈表 headB 的末尾時鸠澈,重新定位到鏈表 headA 的頭結(jié)點(diǎn)柱告。
這樣,當(dāng)它們相遇時笑陈,所指向的結(jié)點(diǎn)就是第一個公共結(jié)點(diǎn)际度。

  • 時間復(fù)雜度:O(M+N)。
  • 空間復(fù)雜度:O(1)O(1)涵妥。
//(雙指針法)
var getIntersectionNode = function(headA, headB) {
    let curA = headA;
    let curB = headB;
    while (curA != curB) {
        curA = curA != null ? curA.next : headB;
        curB = curB != null ? curB.next : headA;
    }
    return curA;
};
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末乖菱,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子蓬网,更是在濱河造成了極大的恐慌窒所,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,194評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件帆锋,死亡現(xiàn)場離奇詭異吵取,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)锯厢,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,058評論 2 385
  • 文/潘曉璐 我一進(jìn)店門皮官,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人实辑,你說我怎么就攤上這事捺氢。” “怎么了剪撬?”我有些...
    開封第一講書人閱讀 156,780評論 0 346
  • 文/不壞的土叔 我叫張陵摄乒,是天一觀的道長。 經(jīng)常有香客問我残黑,道長馍佑,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,388評論 1 283
  • 正文 為了忘掉前任萍摊,我火速辦了婚禮挤茄,結(jié)果婚禮上如叼,老公的妹妹穿的比我還像新娘冰木。我一直安慰自己,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,430評論 5 384
  • 文/花漫 我一把揭開白布踊沸。 她就那樣靜靜地躺著歇终,像睡著了一般。 火紅的嫁衣襯著肌膚如雪逼龟。 梳的紋絲不亂的頭發(fā)上评凝,一...
    開封第一講書人閱讀 49,764評論 1 290
  • 那天,我揣著相機(jī)與錄音腺律,去河邊找鬼奕短。 笑死,一個胖子當(dāng)著我的面吹牛匀钧,可吹牛的內(nèi)容都是我干的翎碑。 我是一名探鬼主播,決...
    沈念sama閱讀 38,907評論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼之斯,長吁一口氣:“原來是場噩夢啊……” “哼日杈!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起佑刷,我...
    開封第一講書人閱讀 37,679評論 0 266
  • 序言:老撾萬榮一對情侶失蹤莉擒,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后瘫絮,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體涨冀,經(jīng)...
    沈念sama閱讀 44,122評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,459評論 2 325
  • 正文 我和宋清朗相戀三年麦萤,在試婚紗的時候發(fā)現(xiàn)自己被綠了蝇裤。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,605評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡频鉴,死狀恐怖栓辜,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情垛孔,我是刑警寧澤藕甩,帶...
    沈念sama閱讀 34,270評論 4 329
  • 正文 年R本政府宣布,位于F島的核電站周荐,受9級特大地震影響狭莱,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜概作,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,867評論 3 312
  • 文/蒙蒙 一腋妙、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧讯榕,春花似錦骤素、人聲如沸匙睹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,734評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽痕檬。三九已至,卻和暖如春送浊,著一層夾襖步出監(jiān)牢的瞬間梦谜,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,961評論 1 265
  • 我被黑心中介騙來泰國打工袭景, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留唁桩,地道東北人。 一個月前我還...
    沈念sama閱讀 46,297評論 2 360
  • 正文 我出身青樓耸棒,卻偏偏與公主長得像朵夏,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子榆纽,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,472評論 2 348