Follow

Follow

·Jun 22, 2022·

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.

解法解析

解法範例

Go

Two pointer
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
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
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
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
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
const dummy = new ListNode(0, head);
let length = 0,
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
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @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`
* 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 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`
* 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 Integer \$n
* @return ListNode
*/
{
\$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 Integer \$n
* @return ListNode
*/
{
\$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:
length: int = 0
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:
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
``````/**
* 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? {

var length: Int = 0

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
``````/**
* 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? {

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