0019-remove-nth-node-from-end-of-list¶

Description¶

Given the head of a linked list, remove the n^th 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?

Solution(Python)¶

# 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: ListNode | None, n: int) -> ListNode | None:
        # 1 2 3 4 5 
        # k =2 
        #  n- k - 1 = 5 - 2 = 3
        # i = 0 1 2 
        #  
        return self.onepass(head,n)
    def twopass(self, head: ListNode | None, n: int) -> ListNode | None:
        total = 0
        cur= head 
        while cur:
            cur = cur.next
            total += 1
        if total == n:
            return head.next

        required = total - n - 1

        
        cur= head
        for _ in range(required):
            if cur.next:
                cur = cur.next
        if cur.next:
            cur.next =  cur.next.next
        return head

    def onepass(self, head: ListNode | None, n: int) -> ListNode | None:
        sentinel = ListNode(0)

        sentinel.next = head
        fast = sentinel
        slow = sentinel

        for i in range(n + 1):
            fast = fast.next
        
        while fast is not None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return sentinel.next
        