題目:

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 = next
class 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 = next
class 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%)

那我們下題見