19题删除链表的指定节点

发表于 | 更新于 | 分类于
本文字数： 1.2k | 阅读时长 ≈ 1 分钟

删除链表的指定节点

难度：中等 思路：窗口法

一、问题描述

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

示例：

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

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

说明：给定的n保证是有效的。

进阶：你能尝试一趟扫描实现吗？

二、问题分析

2.1 逻辑梳理

本题和链表有关，链表是最基本的数据结构，链表中的元素可存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。链表的优势在于插入和删除元素，可以快速完成而不需要移动其他元素。链表由一个个节点组成，节点有两部分，节点的值和下一个节点的地址，尾节点的下一个节点的地址为空。在Python中即None，想要通过一趟扫描删除倒数第n个节点，最有效的方法就是窗口法，指针p，q之间间隔n个节点，然后指针p、q同步往尾部移动，当q到达尾节点时，p后的节点即我们需要删除的目标节点。将p内节点的地址指向下下个节点，删除目标节点，任务完成。

2.2 难点分析

函数传进来的参数和传出去的值都是头结点，在删除节点时，有一个问题需要考虑，怎么保证下下个节点是存在的，如果恰好要删除的就是头节点，是否在程序中考虑到了？其实我刚开始也没考虑，就把示例传进去有正确结果返回高兴的屁颠屁颠以为自己做完了，但上传上去之后被特殊情况搞得晕头转向，仔细分析了很长时间才把head、p、q之间的关系理清楚。

三、代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def removeNthFromEnd(self, head, n):
    if head:
        p=head
        q=head
        # 构建窗口，保证p、q指针之间间隔n个节点
        while n>0 and q != None:
            #当循环结束，如果q=None，则说明需要删除的是头结点。
            q = q.next
            n -= 1
        if q != None:#需要删除的节点不是头结点，p、q正常往链表尾部滑动
            while q.next != None : 
                p = p.next
                q = q.next
        if q == None : #要删除头节点
           head = p.next
        else:
            p.next = p.next.next #正常情况 删除p后面的节点

   return head

复杂度分析：

O(N) N为链表的节点个数