攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

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

從序列中刪除第 N 個節點

攻城獅's photo
攻城獅
·Jun 22, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible