iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 22
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 22

【從面試題學邏輯-22】如何邊拉著狗狗跑步邊刪Node?(leetcode 19. Remove Nth Node From End of List )

題目:
請寫一個方法,來刪掉某個LinkedList中,倒數第N個Node

舉例:
假設LinkedList內有1→2→3→4→5
輸入2的話,應該要把4刪掉,變成1→2→3→5

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


我們今天換下一階段的主題,有關資料結構的題目,其實時間有點趕,視情況再做調整好了/images/emoticon/emoticon06.gif

那這一題其實算很簡單,但正因為很簡單,題目下面多加註了一項挑戰

「你可以只loop一次就完成嗎?」

大家要知道LinkedList不走完全程,是沒辦法知道長度多長的,我們必須要到前一個Node,才能知道是不是還有下一個

所以要找到倒數第n個,直覺上來說就必須要先loop過一次,知道長度後才找的到對應的Node,接著再刪掉它。那這個做法想必大家都能自己做出來,也就不再多敘述了

那到底要如何只跑一次就完成?

不知道大家有沒有看過有人拉著狗狗跑步,通常是下面這種情況,最多就是兩者併排(狗拉人的話嘛……呃,不在本次討論範圍內)

            人
         ∕
      ∕
   ∕
狗
(中間是繩子)

那如果我們把繩子的長度假設為n,假設人站在終點,那狗狗會離人多遠呢?

嗯…………

啊不就是倒數第n個Node的概念嘛!?/images/emoticon/emoticon04.gif

我們上程式碼再做解釋:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) 
    {
        ListNode header = new ListNode(0);
        header.next = head;
        ListNode fast = header , slow = header;
        while(fast.next!=null)
        {
            fast=fast.next;
            if(n<=0) slow=slow.next;
            n--;
        }
        if(slow.next!=null )slow.next=slow.next.next;
        return header.next;
    }
}

大家可以想像這題就是人拉著狗狗跑步,fast就是人,slow就是狗狗

所以當人跑到終點時,狗狗在的地方就是倒數第n個Node面前,這時我們就可以直接把倒數第n個Node刪掉了
(注意LinkedList刪Node的方法,所以上面的程式碼是在那個Node的上一Node)

奇怪,想到這個比喻後文章長度瞬間縮減,搞定了诶?!/images/emoticon/emoticon13.gif


上一篇
【從面試題學邏輯-21】如何邊吃甜甜圈邊理解河內塔程式的遞迴概念?(CTCI 8.6 河內塔)
下一篇
【從面試題學邏輯-23】!吧字數加相來過倒著試(leetcode 2. Add Two Numbers )
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言