حل سوالات استخدامی سایت leetcode.com

Problem: No. 19. Remove Nth Node From End of List #medium

Condition:
Given the header of a linked list, remove the nth node from the end of the list and return its header

Solution:

# class ListNode:
#     def init(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head.next == None:
            return None
        tmp = head
        size = 0
        
        # find the size of the linked list
        while tmp:
            size += 1
            tmp = tmp.next
        tmp = head
        
        #if we have to remove the first node:
        if n == size: 
            return head.next
        
        for i in range(size-n-1):
            tmp = tmp.next
        tmp.next = tmp.next.next
        return head

Explanation:
Determining the list size:

First we go through the entire list to find its size. This is necessary to determine which node needs to be removed.
The size variable keeps track of the number of nodes in the list.
Removing the first node:

If n is equal to the size of the list, it means the first node should be removed. In this case, we return the next node from the head of the list.
Search for a node before the one you want to delete:

If n is not equal to the size of the list, we need to find the node that comes before the nth node from the end. We do this by moving size-n-1 nodes forward in the list.
Removing a node:

We set the next node for the found node so that it points to the next node after the next one, effectively bypassing the node to be deleted.
Returning a new header:

Returning the head of the list. If the first node was deleted, the new header will be the starting node of the list after the delete.
Time and space complexity:
Time complexity: O(L), where L is the length of the list. We go through the list twice: once to count nodes and again to remove a node.
Space complexity: O(1) because we use a constant amount of extra space independent of the size of the input data.

#Code
#interview #LeetCode


🆔 @Python4all_pro