TIP102 Unit 5 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
None
.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.
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:
next
pointer of the second-to-last node to remove the tail.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
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
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`
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.