Remove Nth Node From End of List

题目介绍

LeetCode 19. Remove Nth Node From End of List。

复杂度

时间复杂度: O(L), 空间复杂度: O(1)

解题思路

两次遍历

先遍历出 size，在找到 n 节点删除即可。

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var size = 0
        var node = head
        while node != nil {
            size += 1
            node = node?.next
        }
        if n == size {
            return head?.next
        }
        node = head
        for i in 0..<size-n-1 {
            node = node?.next
        }
        node?.next = node?.next?.next
        return head
    }
}

双指针

我们可以设想假设设定了双指针 first 和 second 的话，当 first 指向末尾的 nil，first 与 second 之间相隔的元素个数为 n 时，那么删除掉 second 的下一个指针即可。

• 添加虚拟头节点 dummy 指向 head
• 初始化双指针 first 和 second，都指向虚拟头节点
• 移动 first，直到 first 与 second 相隔的元素个数为 n
• 同时移动 first 与 second，直到 first 为空
• 将 second 的下一节点指向下下节点

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(-1)
        dummy.next = head
        
        var first: ListNode? = dummy
        var second: ListNode? = dummy
        
        for _ in 0..<n {
            first = first?.next
        }
        
        while(first?.next != nil) {
            first = first?.next
            second = second?.next
        }
        
        second?.next = second?.next?.next
        return dummy.next
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/12/RemoveNthNodeFromEndOfList/