Leetcode-19. 删除链表的倒数第 N 个结点

未分类
698 词

这里采用 计算链表长度法：

  • 第一次遍历链表，得到链表长度 length。

  • 计算要删除节点的正序位置：length - n + 1。

  • 用一个虚拟头节点 dummy 来统一处理删除头结点的情况。

  • 第二次遍历，将要删除的节点跳过，即让前驱节点指向要删除节点的下一个节点。

解题过程

  1. 遍历一次链表，用 length 记录节点总数。

  2. 计算要删除的节点前一个节点的位置，也就是 length - n。

  3. 使用一个 dummy 节点 指向 head，用 tail 指针遍历到该位置。

  4. 直接跳过目标节点：tail.next = tail.next.next。

  5. 返回 dummy.next 作为新链表头。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:

        num=head

        i=0

        while num:

            i+=1

            num=num.next

        p=head

        dummy=ListNode()

        tail=dummy

        for j in range(i-n):

            tail.next=p

            p=p.next

            tail=tail.next

        temp=p.next

        tail.next=temp

        return dummy.next