leetcode with python:19. Remove Nth Node From End of List

题目:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

给定一linked list和一数n,将此linked list的倒数第n个node移除

这题我有想出两个解法
第一个比较直观

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        l=0        ll=head                while ll:            ll=ll.next            l=l+1                    x=l-n        ll2=head        if not x:            return head.next        else:            while x>1:                ll2=ll2.next                x=x-1            ll2.next=ll2.next.next            return head

先算出这个linked list的长度(l)
所以我们知道要被移除的node的前一项是第l-n个node
若l-n==0,则要被移除的是第一个node
所以直接回传head.next即可
否则将第l-n个node的下一项改为其下一项的下一项(跳过删除项)
回传head即可
最后执行时间29ms(faster than 98.22%)

另一个解法则是设立两个指标

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        fast=head        slow=head        for i in range(n-1):            fast=fast.next                pre=None        while fast.next:            fast=fast.next            pre=slow            slow=slow.next                    if pre:            pre.next=pre.next.next            return head        else:            return head.next

设立两指标(fast,slow),两者都在linked list的head
fast先走n-1步,之后再跟slow一起走
当fast走到最后一项的时候,代表slow的位置是要删除的node
期间都有用pre(预设None)纪录slow的上一个node
若pre==None(仍为预设值),则表示要被移除的是第一个node
所以直接回传head.next即可
否则将pre的下一项改为其下一项的下一项(跳过删除项)
回传head即可
最后执行时间33ms(faster than 94.27%)

那我们下题见