Coding interview Essentials

24. \(n^{th}\) node from the end

\(n^{th}\) node from the end

Introduction

The problem presented in this chapter is a particularly interesting one on linked lists. It is often asked during interviews for major tech companies like Amazon and Google and it is therefore worth taking time to ensure we understand and master the solution to this problem.

Problem statement

Given a linked list \(L\) (which definition is shown in Listing [list:delete_duplicates_list:linked_list] at page and an integer \(n\) remove the \(n^{th}\) node from the end of list.


Given \(L=[1,2,3,4]\), and \(n=2\) the function returns: \(L=[1,2,4]\). See Figure 28.1.

Given \(L=[1,2,3,4]\), and \(n=0\) the function returns: \(L=[1,2,4]\). See Figure 28.2.

[fig:node_from_the_end:example1] Figure 1: Removal of the to last element in a singly linked list of length 4.

[fig:node_from_the_end:example2] Figure 2: Removal of the to last element in a singly linked list of length 4. The head pointer needs to be updated.

Clarification Questions

Is \(n\) guaranteed to be a valid node in the list?

Yes you can assume that \(n\) is the index of a valid node in the list.

Discussion

This problem can be broken down into two parts:

  1. Finding out the index of the \(n\)-to last node

  2. Removing a node from the list

These tasks are separate and thus we can solve each of them separately and then use the solution to these two sub-problems to obtain our final answer.

Brute-force

Finding out the the node to be deleted is easy once we know how long the list is. The brute-force approach simply performs a first pass in the list and counts how many nodes it is made of i.e. \(l\). Then it performs another pass but it stops at node \(l-n\) (the n-to-last node) and removes it. Please note that in order to correctly remove a node from a singly linked list we need to have a pointer to the node we want to remove as well as a pointer to its predecessor (variable in the code). This approach can be implemented as shown in Listing [list:node_from_the_end:bruteforce], and it has a time and space complexity of \(O(n)\) and \(O(1)\), respectively.

Listing 1: Sample Caption

int list_length(ListNode* head)
{
  int ans = 0;
  while (head)
  {
    ans++;
    head = head->next;
  }
  return ans;
}

ListNode* remove_nth_node_from_end_bruteforce(ListNode* head, int n)
{
  const int length = list_length(head);
  // we can assume it is always valid/positive

  ListNode *prec = nullptr, *curr = head;

  int index = length - n - 1;
  while (index--)
  {
    prec = curr;
    curr = curr->next;
  }

  ListNode* next = curr->next;
  ListNode* ans  = head;
  if (!prec)
    ans = next;  // we are removing the first node
  else
    prec->next = next;

  return ans;
}

Two pointers

There is however another way of solving this problem that is slightly better even if not in terms of asymptotic complexity. The key issue we have with this problem is that we have to delete a node at index \(l-n\) but we have no idea what \(l\) is and we do not want to compute it explicitly. What we can do is to loop forward with a pointer \(s\) from the head of the list for \(n\) nodes. At this point \(s\) will be at \(n\) node distance from the head and at \(l-n\) from the tail. We now have a way of counting \(n-l\). Let \(f\) be a pointer to the head of the list: we can advance both \(f\) and \(s\) until \(s\) reaches the end of the list. At that point \(s\) had advanced \(l-n\) times and \(f\) crucially will be pointing at the node \(l-n\) i.e. at the n-to-last node.

This idea is implemented in Listing [list:node_from_the_end:twopointers]. Please note that the second , as in the brute-force approach (Listing [list:node_from_the_end:bruteforce]) also needs to keep a pointer to the node preceding the one that needs to be deleted (pointer \(p\) in the code).

The complexity of this implementation is linear in time and constant in space.

Listing 2: Sample Caption

ListNode *remove_nth_node_from_end_two_pointers(ListNode *head, int n)
{
  if (n == 0)
    return head;
  ListNode *s, *f, *p = nullptr;
  s = f = head;

  // advance s n times
  while (n)
  {
    s = s->next;
    n--;
  }

  // now s is at a distance of l-n  from the tail
  while (s)
  {
    ListNode *oldf = f;
    f              = f->next;
    s              = s->next;
    p              = oldf;
  }
  // f points to the node l-n of the list

  ListNode *next = f ? f->next : nullptr;
  if (!p)
  {
    head = next;
  }
  else
  {
    p->next = next;
  }

  return head;
}

Common Variation

List midpoint

Given a linked list \(L\) of length \(l\) (which definition is shown in Listing [list:delete_duplicates_list:linked_list] at page , return the value of the node at position \(\frac{l}{2}\).


Given \(L=[1,2,3,4]\), the function returns \(2\).

Given \(L=[1,5,7,8,9,4,5,6,1,2,4,9,7]\), the function returns \(5\).

This is a very popular variation of the problem described in this chapter. It can be solved using the same methods described in Sections 28.3.1 and 28.3.2 or using an ad-hoc solution (hint: a fast and a slow pointers)