• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

[链表] leetcode 19 删除链表底部的第n个节点[中]


Recommended Posts

给你一个链表,删除链表底部第n个节点,返回链表的头节点。

示例1:

ssj00a4qh3p3836.png

输入:head=[1,2,3,4,5],n=2

输出:[1,2,3,5]

示例2:

输入:head=[1],n=1

输出:[]

示例3:

输入:head=[1,2],n=1

输出:[1]

提示:

链表中的节点数是sz

1=sz=30

0=节点值=100

1=n=sz

高级:可以尝试一次扫描实现吗?

[分析]

1示例给出的链表结构如下图所示:

ttfdkjtflnt3837.png

要删除链表中的一个节点,需要知道它的前一个节点。对于头节点,它没有上一个节点,所以需要定义一个虚拟头节点,如下图所示:

04mzohf1lrs3838.png

这里要删除的是链表中的倒数第二个节点,前一个节点是指针slow指向的节点:

mqsiztuftz53839.png

那么,你如何确定慢指的是哪里呢?这里,我们还需要快速引入指针。当指针fast指向null时,它与指针slow相差两个节点,正好等于:的n(n=2)的值。

m2p252cziac3840.png

那么如何确定fast的位置呢?由于我们只知道链表的头节点,所以需要从头节点开始遍历链表,找到要删除的节点。因此,定义了慢速指针slow和快速指针fast,它们最初指向虚拟头节点。然后,我们先把快速指针快进n 1步。在本例中,n=2,因此fast向前移动了n 1=3步:

hazljl45s0t3841.png

此时,让慢速指针和快速指针同时向前移动,一步一个脚印,直到快速指针快速指向空:

uria41m1qxp3842.png

此时,慢指针指向的节点的下一个节点就是要删除的节点:

pf5wxqwhdsp3843.png

然后,只需将slow所指向的节点的后继指针指向要删除的节点的下一个节点,然后将delNode节点的后继指针指向null,就可以删除倒数第二个节点,或者只需slow.next=slow.next.nex:

qz01mrkfdyz3844.png

#单链表的定义。

# class ListNode:

# def __init__(self,val=0,next=None):

# self.val=val

# self.next=下一个

类别解决方案:

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

dummyHead=ListNode(0,Head)

快,慢=笨蛋,笨蛋

对于范围(n 1):内的I

快=快。下一个

#另一个版本(实际上更快)。

#快,慢=头,笨蛋

#对于范围(n):内的I

# fast=fast .下一个

一边快!=无:

快=快。下一个

慢=慢。下一个

slow.next=slow.next.next

# delNode=slow .下一个

# slow.next=delNode.next

# delNode.next=无

返回傻瓜。下一个

#复杂性分析

#时间复杂度:O(L),其中L是链表的长度。

#空间复杂度:O(1)。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now