حل سوالات استخدامی سایت
leetcode.comProblem: 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
پا 
