Python教程

删除链表的倒数第 N 个结点【python“遍历”LeetCode热门100题】

本文主要是介绍删除链表的倒数第 N 个结点【python“遍历”LeetCode热门100题】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

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

进阶:你能尝试使用一趟扫描实现吗?

示例 1:

 

 

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

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

示例 2:

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

输出:[]

示例 3:

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

输出:[1]

思路分析

        我们知道,如果只遍历一次链表,我们最多只能知道链表的长度,所以常规做法就是遍历两次,第一次获取长度。长度知道后,第二次遍历时就知道去第几个位置了。但显然,这不满足进阶要求:使用一趟扫描。

        我们说的遍历,其实都是默认单指针——所以要想一次扫描获取更多的信息,就是用双指针来做。要找到倒数第N个节点的,我们就直接让两个指针之间的差为N,这样当快指针到达终点时,慢指针所在的位置就是要删除的节点了。当然,要删除某个节点,只知道它的位置是不够的,我们还需要知道这个指针的前一个节点,所以相应的节点也得进行记录。

代码:

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        pre = ListNode()#定义一个超节点
        pre.next = head#把超节点指向头节点
        pp = pre#定义pp暂存超节点的值,因为后续pre值要变化
        left = head#left和right就是快慢指针,也可以理解成左右指针,一个意思
        right = head
        for i in range(n-1):#快指针要先到达比慢指针领先的n位
            right=right.next
        while right.next:#快慢指针同时前进,直到快指针到达终点处
            pre=pre.next#pre就是一直在慢指针的前一个位置,一直前进
            left=left.next#慢指针也一直前进
            right=right.next#快指针一直前进
        pre.next = pre.next.next#删除慢指针所在的节点
        return pp.next#返回超节点的next

        这里道题定义了pre超节点,超节点是做链表问题的一大常用技巧,它可以避免我们以head头节点作为记录时,头节点自身被删除的情况,超节点有一个“置身事外”的功能和特点。

 

这篇关于删除链表的倒数第 N 个结点【python“遍历”LeetCode热门100题】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!