💡 Problem Formulation: This article tackles the common data structure problem: How to retrieve the nth node from the end of a singly linked list using Python. For instance, given a linked list 10->20->30->40->50 and the value of n as 2, the desired output is 40.
Method 1: Two-Pass Algorithm
In the Two-Pass Algorithm, the first pass calculates the length of the linked list, and the second pass finds the nth node from the end by traversing to the (length-n+1)th node from the start. This method is practical when memory usage should be minimized at the cost of the extra time taken for two traversals.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_nth_from_last(head, n):
length = 0
temp = head
while temp:
temp = temp.next
length += 1
temp = head
for i in range(length - n):
temp = temp.next
print(temp.data)
# Example linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
print_nth_from_last(head, 2)
Output: 40
This code first counts the number of nodes in the linked list to calculate its length and then iterates through the list again to reach the (length-n+1)th node, printing its data. This method is straightforward but iterates through the list twice, which may not be efficient for long lists.
Method 2: Two-Pointer Technique
The Two-Pointer Technique involves using two pointers that are placed n nodes apart. The pointers move through the list at the same speed and when the front pointer reaches the end, the other pointer will be at the nth node from the back. This method requires only one pass, making it more time-efficient than the Two-Pass Algorithm.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_nth_from_last(head, n):
main_ptr = ref_ptr = head
count = 0
while(count < n ):
ref_ptr = ref_ptr.next
count += 1
while(ref_ptr):
main_ptr = main_ptr.next
ref_ptr = ref_ptr.next
print(main_ptr.data)
# Example linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
print_nth_from_last(head, 2)
Output: 40
This code snippet leverages the two-pointer method to find the nth node from the end in a single pass. The ref_ptr (reference pointer) is moved n nodes ahead of the main_ptr (main pointer). When ref_ptr reaches the end, main_ptr will be at the correct position to print its data.
Method 3: Recursive Approach
In the Recursive Approach, the list is traversed recursively. Once the recursion hits the base condition, the counter is utilized to identify the nth node from the back on the way up the recursion stack. This method uses system stack memory and might not be suitable for very long lists due to risk of stack overflow.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_nth_from_last(head, n, counter=[0]):
if not head:
return
print_nth_from_last(head.next, n, counter)
counter[0] += 1
if counter[0] == n:
print(head.data)
# Example linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
print_nth_from_last(head, 2)
Output: 40
This recursive function traverses to the end of the list and uses a counter to print the nth node from the end. It’s an elegant solution; however, it’s not the most space-efficient due to the call stack overhead.
Method 4: Reverse the List
Reversing the list and then traversing it to find the nth node is another approach. This solution is not recommended when the list should not be altered or when its data must be preserved in the original order.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_list(head):
prev = None
while head:
next_temp = head.next
head.next = prev
prev = head
head = next_temp
return prev
def print_nth_from_end(head, n):
head = reverse_list(head)
counter = 1
while counter < n:
head = head.next
counter += 1
print(head.data)
# Example linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
print_nth_from_end(head, 2)
Output: 40
After reversing the linked list, the code simply iterates n times to find the nth from end node in the original list (which is now the nth node from start). The operation is not ideal for cases where the original order is important since it alters the linked list.
Bonus One-Liner Method 5: List Conversion
Frequently not the best solution, converting a linked list to a list allows us to leverage Python’s negative indexing to directly access the nth item from the end. This approach should only be used when memory is not a constraint and the convenience of built-in list operations is desired.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def linked_list_to_list(head):
lst = []
while head:
lst.append(head.data)
head = head.next
return lst
def print_nth_from_last(head, n):
lst = linked_list_to_list(head)
print(lst[-n])
# Example linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
print_nth_from_last(head, 2)
Output: 40
By converting the linked list to a Python list, the code takes advantage of Python’s negative indexing to print the nth node from the end, achieving the goal with a simple, readable one-liner inside the function.
Summary/Discussion
- Method 1: Two-Pass Algorithm. Simple to understand. Consumes less memory. Not time-efficient for long lists due to double iteration.
- Method 2: Two-Pointer Technique. Time-efficient with a single traversal. Requires more complex pointer manipulation.
- Method 3: Recursive Approach. Elegant and straightforward recursive solution. Consumes potentially large amounts of stack memory.
- Method 4: Reverse the List. Alters the list, which affects the original list order. Not suitable when list alteration is not allowed.
- Method 5: List Conversion. Easy to write and understand due to Python’s features. Not memory-efficient as it creates a copy of the linked list in list form.