9/24 鏈結串列(刪除從後面數來第N項)

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

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

# 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]:

        p=head

        s=0

        while p:

            p=p.next

            s+=1

       

        x=s-n

        print(f'{head}=s')

        print(f'目標在{x}')

        if x==0:

            '表示首相'

            head=head.next

            return head

        n=1 #從下一個算

        p=head

        while p:

            if n==x:

                p.next=p.next.next

            p=p.next

            n+=1

        return head

       

 ------------------------------------------

# 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]:
        nodelist = []
        ans = head
        i = 0
        while head:
            nodelist.append(head)
            head = head.next
            i+=1
        
        if n == i:
            return ans.next
        elif n == 1:
            temp = nodelist[i-2]
            temp.next = None
            return ans
        else:
            temp = nodelist[i-n-1]
            temp.next = nodelist[i-n+1]
            return ans

-------------------------

# 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]:
        slow = fast = head
        for _ in range(n):
            fast = fast.next
            
        if fast is None:
            return head.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        slow.next = slow.next.next
        return head
-----
Step1: 首先讓fast前進n步,這樣fast就是從尾部數來的第n+1個節點
如果此時fast來到None表示要移除的是標頭
step2:
如果不是 那繼續循環 讓slow和fast同時移動,當fast.next指向None時
slow的下一個節點就是要刪除的節點,改變順序 slow.next=slow.next.next
在return head 就是改變後的鏈結的