Skip to main content
Hashnode不工程的攻城獅

Command Palette

Search for a command to run...

LeetCode Solution, Medium, 19. Remove Nth Node From End of List

從序列中刪除第 N 個節點

Published
攻
攻城獅

I am not a programmer just a leaner. Writing JavaScript, Python, and Go and doing something on Kubernetes.

Part of seriesLeetCode Solution

19. Remove Nth Node From End of List

題目敘述

Given the head of a linked list, remove the n**th node from the end of the list and return its head.

Example:

remove_ex1.jpeg

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow up: Could you do this in one pass?

Hint 1:

Maintain two pointers and update one with a delay of n steps.

題目翻譯

給定一個連結序列 head，從中刪除由結尾算起來第 n 個節點，並回傳 head。

解法解析

這個題目主要用兩種解法，第一種是 Two pointer 和第二種 One Pass。但不管這兩種其實重點就是要先知道其序列的長度 L。因為是要從結尾往前推的第 n 個結點來算，而不管是 two pointer 還是 one pass 都只是由這結果往回推算或是紀錄第 n 個節點而已。

這邊要特別提到的是，滿多人提到官方的解法不能算是 one pass，因為用到兩個迴圈。但是執行上我個人認為的確可以說是 one pass，他只是中間切斷放到另一個迴圈來跑。但這個定義就見仁見智了。

解法範例

Go

Two pointer
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    first := head
    length := 0

    for first != nil {
        length++
        first = first.Next
    }

    first = dummy
    for i := length - n; i > 0; i-- {
        first = first.Next
    }
    first.Next = first.Next.Next
    return dummy.Next
}
One pass
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    first := dummy
    second := dummy

    for i := 0; i <= n; i++ {
        first = first.Next
    }

    for first != nil {
        first = first.Next
        second = second.Next
    }
    second.Next = second.Next.Next
    return dummy.Next
}

JavaScript

Two pointer
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let length = 0,
        first = head;
    while (first) {
        length++;
        first = first.next;
    }

    first = dummy;
    for (let i = length - n; i > 0; i--) {
        first = first.next;
    }

    first.next = first.next.next;
    return dummy.next;
};
One pass
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let first = dummy,
        second = dummy;
    for (let i = 0; i < n + 1; i++) {
        first = first.next;
    }

    while (first !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
};

Kotlin

Two pointer
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummy: ListNode = ListNode(0).apply { next = head }
        var first: ListNode? = head
        var length: Int = 0

        while (first!!.next != null) {
            length ++
            first = first!!.next
        }

        first = dummy
        for (i in (length - n) downTo 0) {
            first = first!!.next
        }

        first!!.next = first?.next?.next
        return dummy.next
    }
}
One pass
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummy: ListNode = ListNode(0).apply { next = head }
        var first: ListNode? = dummy
        var second: ListNode? = dummy

        for (i in 0 until n) {
            first = first!!.next
        }

        while (first!!.next != null) {
            first = first!!.next
            second = second!!.next
        }

        second!!.next = second?.next?.next
        return dummy.next
    }
}

PHP

Two pointer
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n)
    {
        $dummy = new ListNode(0, $head);
        $first = $head;
        $length = 0;
        while (!is_null($first)) {
            $length++;
            $first = $first->next;
        }

        $first = $dummy;
        for ($i = $length - $n; $i > 0; $i--) {
            $first = $first->next;
        }

        $first->next = $first->next->next;
        return $dummy->next;
    }
}
One pass
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n)
    {
        $dummy = new ListNode(0, $head);
        $first = $dummy;
        $second = $dummy;

        for ($i = 0; $i < $n + 1; $i++) {
            $first = $first->next;
        }

        while (!is_null($first)) {
            $first = $first->next;
            $second = $second->next;
        }

        $second->next = $second->next->next;
        return $dummy->next;
    }
}

Python

Two pointer
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy: ListNode = ListNode(0, head)
        length: int = 0
        first: ListNode = head
        while first is not None:
            length += 1
            first = first.next

        first = dummy
        for _ in range(length - n, 0, -1):
            first = first.next

        first.next = first.next.next
        return dummy.next
One pass
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy: ListNode = ListNode(0, head)
        first: ListNode = dummy
        second: ListNode = dummy

        for _ in range(n + 1):
            first = first.next

        while first is not None:
            first = first.next
            second = second.next

        second.next = second.next.next
        return dummy.next

Rust

Swift

Two pointer
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */


class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard let head = head else { return nil }

        let dummy = ListNode(0, head)
        var length: Int = 0
        var first: ListNode? = head

        while first != nil {
            length += 1
            first = first?.next
        }

        first = dummy
        for _ in 0..<(length - n) {
            first = first?.next
        }

        first!.next = first?.next?.next
        return dummy.next
    }
}
One pass
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard let head = head else { return nil }

        let dummy = ListNode(0, head)
        var first: ListNode? = dummy
        var second: ListNode? = dummy

        for _ in 0...n {
            first = first?.next
        }

        while first != nil {
            first = first?.next
            second = second?.next
        }

        second!.next = second?.next?.next
        return dummy.next
    }
}
#leetcode#programming-blogs#programming#learning#learn-coding

Comments

Join the discussion

No comments yet. Be the first to comment.

LeetCode Solution

Part 22 of 50

A collection of leetcode solustion

Up next

LeetCode Solution, Easy, 160. Intersection of Two Linked Lists

兩個連結序列的交會點

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

現在應該開始有很多人想要踏入軟體工程的領域，但在進入這個領域之前，覺得先了解一些名詞，可以在入門時更有方向也更知道要用什麼關鍵字去找尋有用的資訊。這篇文章就是想要幫助想要入門的人理解一些軟體工程裡的專有名詞。 作業系統 這一區塊主要解釋跟作業系統層面相關的名詞 英文中文解釋 Operation system 簡稱 OS | 作業系統 | 就是電腦的作業系統，是三大作業系統分別是：Linux、Windows、macOS | | Linux | | 自由和開放原始碼的 UNI...

May 10, 2023

我的 MacBook Pro (Apple Silicon) 設定

現在開始因為 ChatGPT 的出現，各種 AI 助手的功能都跑出來了。想想自己用了許久的環境設定也應該要來重新審視和建立新的開發環境了，僅此紀錄我個人的環境配置步驟和設定。 環境前置步驟 還原 MacBook Pro 至全新環境 macOS（全部資料刪除） 設定好初始設定後，登入 Apple ID 進入 App Store 確定 macOS 版本和預設 APP 都更新到最新 macOS 版本 到系統設定調整所有設定至個人習慣的設定 三指拖移 觸控板手勢開啟 防火牆開啟 輸入法設定...

Apr 25, 2023

ChatGPT 下的發展預想

從 ChatGPT 問世到現在，有許許多多的文章和討論出來。先從最早的 Google 要完蛋了，到後來的工作要被取代了，工程師失業了。 我就比較沒有想要馬上出來評論一下，我喜歡讓子彈飛一會兒。跟討論一下我自己比較在意的討論點。 Google 為什麼慢了? 結論：因為他需要更小心 很多人說 Google 怎麼被微軟搶先了一步。剛開始 Bing 說要加上 AI 的時候大家都在說 Google 怎麼慢了。我就馬上跑去看 OpenAI 的網站，靠北呀啊就 Azure 贊助的。那當然在正式上線 ChatG...

Mar 23, 2023
不

不工程的攻城獅

223 posts

I am not a programmer because I am not good at programming. But I do programming. Love to learn new things. An animal lover and a dancer. My oshi is 潤羽るしあ.