Remove Nth Node From End of List

I occasionally solve algorithm questions on Leetcode as a fun exercise. I recently wrote about a dynamic programming question I solved, and I thought it would be fun to share another one. This time it’s a simple linked list question.

Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

I started off just creating a skeleton of the solution that allows me to run the examples and see the output.

class ListNode
  attr_accessor :val, :next
  def initialize(val = 0, _next = nil)
    @val = val
    @next = _next
  end
end

# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
  head
end

def print_list(head)
  result = []
  while head
    result << head.val
    head = head.next
  end
  pp result
end

print_list(remove_nth_from_end(ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5))))), 2))
print_list(remove_nth_from_end(ListNode.new(1), 1))
print_list(remove_nth_from_end(ListNode.new(1, ListNode.new(2)), 1))

Now onto the actual solution. Since this is a linked list we can’t simply walk all the way to the end of the list and then backtrack. Instead I found it useful to think of the desired end state of the algorithm - we want to end up with a pointer pointing to the node before the nth node from the end of the list. So in the example of [1, 2, 3, 4, 5] we want a pointer at the 3 node, which is the third node from the end, in order to be able to do p.next = p.next.next.

The trickiest part of this algorithm is the edge cases - I got a bit stuck on how to solve for [1, 2] with n = 1 (the result being [1]) and n = 2 (the result being [2]). Then I realized that when the size of the list is the same as n, that is a special case where you return head.next. In all the other cases I can modify the list and return head.

# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
  p = head
  list_size = 0
  until p.nil?
    list_size += 1
    p = p.next
  end

  if n == list_size
    head.next
  else
    p = head
    (list_size - n - 1).times { p = p.next }
    p.next = p.next.next
    head
  end
end

I didn’t really enjoy doing this algorithm as much as the dynamic programming one. I’m doing the algorithms because it’s something I enjoyed doing when I was a student, and it helps to bring back some of the joy of programming for it’s own sake. Maybe I’ll stick to the ‘hard’ questions, or at least questions where a brute force answer is easy but an optimal one takes some creativity.

Ruby Algorithms