Remove Last - codepath/compsci_guides GitHub Wiki

TIP102 Unit 5 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15 mins
  • 🛠️ Topics: Linked Lists, Traversal

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • What happens if the linked list is empty?
    • Return None.
  • What happens if there is only one node in the list?
    • Return None, since the only node will be removed.
HAPPY CASE
Input: Node("A") -> Node("B") -> Node("C")
Output: Node("A") -> Node("B")
Explanation: The last node "C" is removed.

EDGE CASE
Input: Node("A")
Output: None
Explanation: The only node is removed.

M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems, we want to consider the following approaches:

  • Iterative traversal: We will need to traverse the list to find the second-to-last node.
  • Pointer manipulation: Adjust the next pointer of the second-to-last node to remove the tail.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the list to find the second-to-last node, then set its next pointer to None.

1) If the list is empty (`head` is `None`) or contains only one node, return `None`.
2) Otherwise, traverse the list until the second-to-last node is reached.
3) Set the `next` pointer of the second-to-last node to None, effectively removing the last node.
4) Return the modified list's head.

⚠️ Common Mistakes

  • Forgetting to handle the case where the list has only one node.
  • Misplacing pointers, which could break the list structure.

I-mplement

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def delete_tail(head):
    if head is None or head.next is None:
        return None
    
    current = head
    while current.next and current.next.next:
        current = current.next
    
    current.next = None
    return head

R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

Input: Node("A") -> Node("B") -> Node("C")
Expected Output: Node("A") -> Node("B")
Steps:

The current pointer starts at Node("A").
The loop moves current to Node("B").
The next pointer of Node("B") is set to None.
Example 2:

Input: Node("A")
Expected Output: None
Steps:

Since the list has only one node, the function returns `None`

E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because we need to traverse the entire list.

  • Space Complexity: O(1) because we only use a fixed amount of space regardless of the input size.