Logicmojo - Updated Aug 28, 2021
Problem Statement: Find xth Node from End of Linked List
Given a linked list, find the xth node from the end.
Example: Linked list: 1→2→3→4; x: 2
Result: 1→2→4
Approach: Using Two pointer
With a singly linked list, the only way to find the end of the list, and thus the x'th node from the end, is to actually iterate all the way to the end. The challenge here is attemping to find the solution in only one pass. A naive approach here might be to store pointers to each node in an array, allowing us to calculate the n'th from the end once we reach the end, but that would take O(M) extra space, where M is the length of the linked list.
In order to solve this problem in only one pass and O(1) extra space, however, we would need to find a way to both reach the end of the list with one pointer and also reach the x'th node from the end simultaneously with a second pointer.
C++ Implementation:
ListNode *removexthFromEnd(ListNode *head, int n) { if (!head) return nullptr; ListNode new_head(-1); new_head.next = head; ListNode *slow = &new_head, *fast = &new_head; for (int i = 0; i < n; i++) fast = fast->next; while (fast->next) { fast = fast->next; slow = slow->next; } ListNode *to_de_deleted = slow->next; slow->next = slow->next->next; delete to_be_deleted; return new_head.next; }
Python Implementation:
class Node: def __init__(self, val): self.val = val self.next = None class Solution(object): def removeNthFromEnd(self, head, n): slow = head # finally point to the previous node of the target node fast = head # finally point to the last node for i in range(n): # let the fast pointer move n steps ahead of the slow pointer fast = fast.next # This situation would happen when we are required to del the first node (n = len(List)) # Also, it can handle the [] case if not fast: return slow.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head def display(head): while head: print(head.val, end = ' -> ') head = head.next print('X') if __name__=='__main__': head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) head.next.next.next.next.next.next = Node(7) ob1 = Solution() head1 = ob1.removeNthFromEnd(head, 2) display(head1)
Time Complexity: O(n)
Space Complexity: O(1)
With this article at Logicmojo, you must have the complete idea of solving Find xth Node from End of Linked List problem.