LeetCode 0019.删除链表的倒数第N个节点

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

题目描述

示例1：

1
2


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

示例2：

1
2


输入：head = [1], n = 1
输出：[]

示例 3：

1
2


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

思路

题目要求

题目给定一个单链表，要求删除倒数第n个节点
返回删除后的链表的头节点

暴力解法：遍历一遍链表，获知链表的总长度L，第二遍遍历删除从开头数起第(L-n+1)个节点。时间复杂度为O(2n)。

模式识别：

设计链表的特殊位置，考虑快慢指针
要删除链表节点，找到它的前驱节点

双指针法：先让快指针走n步，此时快慢指针之间距离为n。然后快慢指针同时移动，当快指针移动到 nil时，慢指针指向的节点的后一个节点就是要删除的倒数第n个节点。一遍遍历，时间复杂度为O(n)。

注意

使用虚拟头结点，这样方面处理删除实际头结点的逻辑
定义fast指针和slow指针，初始值为虚拟头结点
返回dummyNode+1，因为head可能会被删除

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyNode := new(ListNode)
    dummyNode.Next = head
    slowIndex, fastIndex := dummyNode, dummyNode
    for i := 0; fastIndex != nil; fastIndex = fastIndex.Next {
        if i > n {
            slowIndex = slowIndex.Next
        }
        i++
    }
    slowIndex.Next = slowIndex.Next.Next
    return dummyNode.Next
}

Link

GitHub