Remove Nth Node From End Of List

题目描述

删除链表的倒数第N个节点：

删除给定链表的倒数第N个节点，返回链表头节点。

示例：

输入：head = [1, 2, 3, 4, 5], n = 2
输出：[1, 2, 3, 5]

解法

go的链表节点定义为：

type ListNode struct {
    Val  int
    Next *ListNode
}

解法一：两次遍历

先求出链表长度，再删除指定链表。代码略。

解法二：数组或栈

将链表节点放入数组，然后根据根据下标删除指定节点。代码略。

解法三：快慢指针

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    slow, fast := dummy, dummy
    // 让快慢指针相差n个节点
    counts := 0
    for counts < n && fast != nil {
        fast = fast.Next
        counts++
    }

    if fast == nil {
        return dummy.Next
    }

    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }

    slow.Next = slow.Next.Next
    return dummy.Next
}