描述

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

示例

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

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

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

尝试使用一趟扫描实现

 

思路

双指针。

第一个指针从链表开头向前移动n+1步,第二个指针指向链表开头。

两个指针保持这个恒定的间隔同时移动,直到第一个指针到达最后一个结点。这个时候第一个指针就是指向该删除的结点的上一个结点。

处理的有点复杂的地方是,第二个结点可能不存在,因为倒数第n个结点可能就是开头的结点,这个地方判断一下就好了。

 

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

        first = head
        val = head
        for i in range(n):
            val = val.next

        if val is None:
            return head.next
        prior = head
        while val.next is not None:
            val = val.next
            prior = prior.next
        prior.next = prior.next.next
        return first

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄