LeetCode 0019

题目

19. Remove Nth Node From End of List 给定一个链表，删除链表的倒数第 n 个节点，只遍历一次。

思路

初见

在不考虑只遍历一次的进阶条件下，使用两个指针，第一次遍历完整个链表取到链表中总计 x 个元素。第二次遍历到第 x - n - 1 个链表元素，假设为 node，执行 node.next = node.next.next，得解。

再看

考虑只遍历一次这个条件，同样使用两个指针，但不能在一个指针遍历完成之后，再重新遍历，那么就需要两个指针同时工作。 思路如下：

1. 定义两个指针 fast 和 sow
2. fast 指针先走 n 个元素
3. 之后当 fast 的 next 节点不为 nil 时，fast 和 slow 同时往前
4. 此时 slow 指针指向的就是倒数第 n + 1 的链表元素 到这里，看似只要执行 slow.next = slow.next.next 就可以得到正确结果，然而在跑了测试用例之后发现，[1, 2] / 2 和 [1] / 1 的输入无法通过。如果当 fast 先走了 n 步时，恰好走到了最后一个节点，此时 slow 节点还没有移动，则说明链表中需要移除倒数第 n 个节点恰好是第一个节点。实现代码如下

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fast = head, slow: ListNode? = nil, n: Int = n
    while let nd = fast {
        if n != 0 {
            fast = nd.next
            n -= 1
            continue
        }
        fast = fast?.next
        slow = slow == nil ? head : slow?.next
    }
    if slow == nil {
        return head?.next
    } else {
        slow?.next = slow?.next?.next
        return head
    }
}