You are given two ListNodes of a doubly linked list. Write a function pop_tail which removes the tail of the linked list in $O(1)$ time. Return the head and tail of the linked list as a list. If the linked list is empty after removal, return None.

A ListNode is defined as:

class ListNode:
	value: ListNode = None
  next: ListNode = None
  prev: ListNode = None

Example:

Input:

3 -> 2 -> 4 -> 5 -> 7
head = ListNode(3)
tail = ListNode(7)

Output:

def pop_tail(head: ListNode, tail:ListNode) -> [ListNode(3), ListNode(5)]

Solution

The solution to this problem is rather elegant. First, to ensure that our algorithm is $O(1)$, all we need to do is to never have any operations that iterate through the entire list. To do that, we must leverage the fact that our linked list is a doubly linked list.

First, we must set the node before our tail as the new tail. To make sure that it is indeed the tail, we should remove the old tail’s reference on node_before_tail.next and set it to None.

Lastly, all we need to make sure is handle the edge case where the list turns empty after removing the tail. All you need to notice is that a list with one element basically has their head node be the same as their tail node. All you need to due is check for their equality and return None if they are equal (as essentially, the list is now empty).

def pop_tail(head: ListNode, tail:ListNode) -> [ListNode, ListNode]:
    # Let's check if the head is the same as the tail node.
    # If it is, we know that our list only has one element.

    if head is tail:
      return None

    # else, let's try to remove the tail
    node_before_tail = tail.prev
    node_before_tail.next = None # remove the tail from the link
    return [head, node_before_tail]