π‘ Problem Formulation: This article discusses how to find the k-th last element in a singly linked list using Python. For instance, given a linked list node1 -> node2 -> node3 -> node4 -> node5
and k=2
, the desired output would be node4
.
Method 1: Two-Pass Algorithm
The two-pass algorithm involves two iterations: the first one to count the total number of nodes in the linked list and the second to locate the k-th last node. This is a straightforward concept that’s easy to understand and implement for beginners.
Here’s an example:
class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def find_kth_last(head, k): length = 0 current = head while current: length += 1 current = current.next target = length - k current = head while target > 0: current = current.next target -= 1 return current.value # Example Linked List: 1 -> 2 -> 3 -> 4 -> 5 nodes = [ListNode(i) for i in range(1, 6)] for i in range(4): nodes[i].next = nodes[i+1] print(find_kth_last(nodes[0], 2))
Output: 4
This snippet constructs a sample linked list and then invokes the find_kth_last()
function to find the 2nd last node. The first loop calculates the total number of nodes, and then we use that number to find the k-th last element in a second pass.
Method 2: Recursive Approach
The recursive approach solves the problem by reaching the end of the list through recursion and then counting back from the last element to locate the k-th last node. It uses the call stack as storage to keep track of the traversal. It’s slightly more complex but removes the need to know the total length beforehand.
Here’s an example:
def find_kth_last_recursive(node, k, counter=[0]): if not node: return None result = find_kth_last_recursive(node.next, k, counter) counter[0] += 1 if counter[0] == k: return node return result # Example usage with the same linked list as above print(find_kth_last_recursive(nodes[0], 2).value)
Output: 4
This code uses recursion to traverse to the end of the list and uses a mutable default argument, counter
, as a counter which increments on the unwind of recursion. When the counter equals k, the current node is the k-th last node.
Method 3: Two Pointers Approach
The two pointers approach is more efficient. It involves moving one pointer k
nodes into the list, and then moving a second pointer from the head until the first pointer reaches the end. When the first pointer hits the end, the second pointer will be on the k-th last node.
Here’s an example:
def find_kth_last_two_pointers(head, k): lead, follow = head, head for _ in range(k): if not lead: return None lead = lead.next while lead: lead, follow = lead.next, follow.next return follow.value # Example usage with the same linked list as Method 1 print(find_kth_last_two_pointers(nodes[0], 2))
Output: 4
This snippet uses two pointers to avoid counting the total length of the list. The lead
pointer advances k steps ahead of the follow
pointer, ensuring that when lead
reaches the end of the list, follow
is at the k-th last node.
Method 4: Reverse the list
Another strategy is to reverse the linked list, find the k-th node in the reversed list, and then reverse it back to its original form if needed. This method is not recommended for singly linked lists as it mutates the list, but it’s a good exercise to understand list operations.
Here’s an example:
def reverse_list(head): prev = None current = head while current: nxt = current.next current.next = prev prev = current current = nxt return prev def find_kth_last_reverse(head, k): reversed_head = reverse_list(head) current = reversed_head for _ in range(k-1): if not current: return None current = current.next return current.value # Example usage with the same linked list as Method 1 print(find_kth_last_reverse(nodes[0], 2))
Output: 4
This code first reverses the list, traverses it to find the k-th node, and, if necessary, reverses the list again to return it to its original state. This method is straightforward but can be destructive if the reversal is not handled properly.
Bonus One-Liner Method 5: Using Collections.deque
Using Python’s collections.deque
, which provides an efficient way to handle double-ended queues, we can solve this problem by maintaining a fixed-size queue that eventually contains the last k nodes of the list.
Here’s an example:
from collections import deque def find_kth_last_deque(head, k): queue = deque(maxlen=k) current = head while current: queue.append(current.value) current = current.next return queue[0] if len(queue) == k else None # Example usage with the same linked list as Method 1 print(find_kth_last_deque(nodes[0], 2))
Output: 4
The snippet uses deque
from Python’s collections module with a maxlen
set to k
. As the list is traversed, the queue keeps the last k
elements seen, and when the traversal is complete, the k-th last element is at the start of the deque.
Summary/Discussion
- Method 1: Two-Pass Algorithm. Simple, intuitive. Requires list traversal twice. Inefficient for very large lists.
- Method 2: Recursive Approach. Elegant with no need for list length. Potentially high call stack usage, which might be problematic for very long lists.
- Method 3: Two Pointers Approach. Efficient and often considered the best practice. Single traversal. Can be confusing to understand at first.
- Method 4: Reverse the list. Teaches list reversing but mutates the list. Risks altering the original data structure.
- Method 5: Using Collections.deque. Quick and clever. Relies on Python standard libraries. Could use extra memory for the deque structure.