<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

以下为我的天梯积分规则:


每日至少一题:一题积分+10分

若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)

若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)


初始分为100分

若差一天没做题,则扣积分-10分(周六、周日除外注:休息)

坚持!!!


初级算法

刷题目录

链表


<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

题干

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

示例1:

<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

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

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

示例2:

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

输出:[]

示例3:

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

输出:[1]

提示:

<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

双指针法

分析:

根据题干的要求,我们需要删除倒数第n个节点,在返回头结点。只需要找到倒数第n个节点,将其删除,再返回。

说真的不难,直接用双指针,来!

借用一下大佬的草图

<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python

# 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:
        # 定义哑终端,用于前项循环
        dummy = ListNode(0)
        dummy.next = head

        # 设置两个指针
        fast = head
        slow = dummy
        # 移动fast到n步
        for i in range(n):
            fast = fast.next
       
        # 快慢节点同时走,循环到fast的末尾
        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

卷啊卷,一直卷!~

<LeetCode天梯>Day025 删除链表的倒数第N个节点(双指针) | 初级算法 | Python


上一篇:datenode节点超时时间设置,Hadoop启动不正常,HDFS冗余数据块的自动删除,NameNode安全模式问题,ntp时间服务同步,机架感知配置


下一篇:如何在Spark中实现Count Distinct重聚合