Find the kth-to-last element of a singly linked list

Question

I wrote this code for finding the \$k\$th-to-last element in a singly linked list.

class Node:
 def __init__(self, v = None, next = None):
 self.v = v
 self.next = next
a = Node("Australian Sheperd")
b = Node("Beagle")
c = Node("Cairne Terrier")
d = Node("Dobermann")
e = Node("English Mastiff")
a.next = b
b.next = c
c.next = d
d.next = e
count = 1
def kthToLastNode(k, root):
 global count
 if root.next:
 count = kthToLastNode(k, root.next)
 if count == k:
 print(root.v)
 return count + 1

For example:

>>> kthToLastNode(3,a)
Cairne Terrier
6

When called on a list with \$n\$ nodes, the code goes all the way through the list, recursing \$n\$ times, using \$\Theta(n)\$ stack space, and returning \$n\$ times. Is there a way to improve the space performance of the function?

Answer 1

1. Review

1. There is no docstring. What does kthToLastNode do? What does it return? A docstring would explain that you have to pass k=1 to get the last item, k=2 to get the second-to-last item, etc.

2. It would be more useful, I think, if kthToLastNode returned the \$k\$th-to-last node instead of printing the node's value and returning the length of the linked list.

3. If you pass a value for k that's out of range (for example, longer than the length of the linked list) then there should be some error handling. For example, you might raise an exception.

4. Using a global count means that kthToLastNode can only be called once: if you call it again count has the wrong value and the function prints nothing and returns the wrong result.

2. Alternative approaches

Instead of recursing, iterate! Here are two implementation ideas.

1. Iterate over the list twice, first to find its length, and then to find the \$k\$th-to-last node. It would be worth making a separate function to find the length: this will make the code clearer, and we might have other places where we need to find the length, so if we make a function we'll be able to reuse it.

   def linked_list_length(node):
    "Return the length of the linked list starting at node."
    length = 0
    while node:
    length += 1
    node = node.next
    return length
   def kth_to_last_node(node, k):
    """Return the kth-to-last node of the linked list starting at node.
    Pass k=1 for the last node, k=2 for the next-to-last node, and so
    on. Raise IndexError if k is out of range.
    """
    length = linked_list_length(node)
    if k < 1 or k > length:
    raise IndexError("index out of range")
    for _ in range(length - k):
    node = node.next
    return node
   

   This uses \$O(1)\$ space but has to traverse the list twice.

2. Append the nodes one by one to a queue of length \$k\,ドル so that when we reach the end of the list, the first element of the queue will be the \$k\$th-to-last node. We can implement the queue using collections.deque.

   from collections import deque
   def kth_to_last_node(node, k):
    """Return the kth-to-last node of the linked list starting at node.
    Pass k=1 for the last node, k=2 for the next-to-last node, and so
    on. Raise IndexError if k is out of range.
    """
    queue = deque(maxlen=k)
    while node:
    queue.append(node)
    node = node.next
    if k < 1 or len(queue) != k:
    raise IndexError("index out of range")
    return queue[0]
   

   This traverses the list once but uses \$O(k)\$ space.

3. General discussion

Recursion and iteration are very similar: anything you can do with one, you can do with the other. In some cases the code is simpler and clearer if you use recursion, in other cases if you use iteration, and sometimes it doesn't make much difference. So it's hard to give general advice: there's no real substitute for trying both and seeing which you like better! For example, here's a case where recursion was nicer.

In the case of singly linked lists, it's worth pointing out that we don't have much need for this data structure in Python, because the built-in list data type is nearly always better than a linked list. You can get the \$k\$th-to-last element of the list a by writing a[-k], and this takes \$O(1)\$ time and \$O(1)\$ space.

The cases in which we do want to use linked lists in Python are those in which we need to efficiently insert new elements into the middle of a list. See this answer for a rare example. But in these cases we probably don't need to find the \$k\$th-to-last element.

• Raksha: Thank you. I thought about going the way of calculating the length first, as you said. Which do you think is better? I'm still learning about pros and cons or iterative vs recursive approaches and it's not always clear to me which one is best, like when it's more appropriate to trade off space vs time.
• Gareth Rees: @Raksha: See updated answer.