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

πŸ’‘ 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.