给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

方法一，使用数组辅助

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution:

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        a = []

        while head:

            a.append(head)

            head = head.next

        if n == len(a):

            new = a[0].next

            a[0].next = None

            return new

        if n == 1:

            a[-2].next = None

            return a[0]

        a[-n-1].next = a[-n+1]

        return a[0]

方法二，使用快慢指针

双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

设置虚拟节点 dummyHead 指向 head

设定双指针 p 和 q，初始都指向虚拟节点 dummyHead

移动 q，直到 p 与 q 之间相隔的元素个数为 n

同时移动 p 与 q，直到 q 指向的为 NULL

将 p 的下一个节点指向下下个节点

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        dummyHead = ListNode(0)

        dummyHead.next = head

        p = dummyHead

        q = dummyHead

        for i in range(n+1):

            q = q.next

        while(q):

            p = p.next

            q = q.next

        p.next = p.next.next

        return dummyHead.next

巴特西

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

方法一，使用数组辅助

方法二，使用快慢指针

最新文章

热门文章