# 5 Best Ways to Find the k-th Last Node of a Linked List in Python

Rate this post

π‘ 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

length = 0
while current:
length += 1
current = current.next
target = length - k
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):
for _ in range(k):
return None
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
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev

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

queue = deque(maxlen=k)
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.