LeetCode ＃19.删除链表的倒数第N个结点

力扣 | 19.删除链表的倒数第N个结点

题目截图

 

方法一：两次遍历

第一次遍历计算链表的长度得到长度length，然后利用k=length-n取得要删除的结点处的位置。

第二次遍历，到达k位置的时候利用cur.next = cur.next.next将结点指针指向要被删除结点的后面一个。这样就成功删除了。

考虑到只有一个节点要被删除的情况，所以在头结点前还设置了一个节点ans，最后返回ans.next。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length, cur = 0, head
        while cur:
            cur = cur.next
            length += 1

        ans = ListNode(0,head)
        cur = ans
        k = length - n
        while k :
            cur = cur.next
            k -= 1
        cur.next = cur.next.next
        return ans.next

完整测试代码

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length, cur = 0, head
        while cur:
            cur = cur.next
            length += 1

        ans = ListNode(0,head)
        cur = ans
        k = length-n
        while k:
            cur = cur.next
            k -= 1
        cur.next = cur.next.next
        return ans.next

def create_linked_list(nums):
    if len(nums) == 0:
        return None
    head = ListNode(nums[0])
    cur = head
    for i in range(1, len(nums)):
        cur.next = ListNode(nums[i])
        cur = cur.next
    return head


def print_linked_list(list_node):
    if list_node is None:
        return

    cur = list_node
    while cur:
        print(cur.val, '->', end=' ')
        cur = cur.next
    print('null')

class main():
    a = Solution()
    nums = [1, 2, 51, 9, 26, 72, 4, 8]
    n = 3
    h = create_linked_list(nums)

    b= a.removeNthFromEnd(head=h,n=n)
    print(nums)
    print("删除倒数第{0}个结点,该结点数值为{1}".format(n, nums[len(nums)-n]))
    print()
    print("删除后链表的结果如下：")
    print_linked_list(b)

if __name__ == '__main__':
    main()

方法二：栈

先将整个链表存储栈中，然后利用栈的特性，将末尾的元素出栈。再找到出栈后的栈顶元素，该结点就是被删除结点的前一个结点，使该节点指向被删除结点的后一个结点即可成功删除指定结点。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        ans = ListNode(0,head)
        stack = list()
        cur = ans
        while cur:
            stack.append(cur)
            cur = cur.next

        for i in range(n):
            stack.pop()
        prev = stack[-1]
        prev.next = prev.next.next
        return ans.next

方法三：双指针

利用先后两个指针遍历。无需计算链表长度。

因为要求删除链表倒数第n个结点，那么第一个指针比第二个指针提前n个结点，然后一起遍历，当第1个指针到达链表尾端时，第二个指针刚好指在倒数第n个结点上。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        ans = ListNode(0,head)
        first = head
        for i in range(n):
            first = first.next

        second = ans
        while first:
            first = first.next
            second = second.next

        second.next = second.next.next
        return ans.next