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:

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 Solution, Medium, 19. Remove Nth Node From End of List

Comments

LeetCode Solution

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

More from this blog

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

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

19. Remove Nth Node From End of List

題目敘述

題目翻譯

解法解析

解法範例

Go

Two pointer

One pass

JavaScript

Two pointer

One pass

Kotlin

Two pointer

One pass

PHP

Two pointer

One pass

Python

Two pointer

One pass

Rust

Swift

Two pointer

One pass

Command Palette

Comments

LeetCode Solution

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

More from this blog

19. Remove Nth Node From End of List

題目敘述

題目翻譯

解法解析

解法範例

Go

Two pointer

One pass

JavaScript

Two pointer

One pass

Kotlin

Two pointer

One pass

PHP

Two pointer

One pass

Python

Two pointer

One pass

Rust

Swift

Two pointer

One pass