Insert Node as Second Element - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 5-10 mins
  • 🛠️ Topics: Linked Lists, Insertion

1: U-nderstand

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

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What happens if the linked list contains only one element?
    • The new node will become the second element, with the single initial element remaining the head.
HAPPY CASE
Input: head = Node("banana") -> Node("blue shell") -> Node("bullet bill"), val = "red shell"
Output: Node("banana") -> Node("red shell") -> Node("blue shell") -> Node("bullet bill")
Explanation: The node with value "red shell" is correctly inserted as the second node.

EDGE CASE
Input: head = Node("banana"), val = "red shell"
Output: Node("banana") -> Node("red shell")
Explanation: The new node is inserted as the second element after the single existing node.

2: 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:

  • Insertion of nodes in a linked list
  • Updating pointers to maintain the correct sequence

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Insert a new node after the head of the linked list by updating the next pointers of the relevant nodes.

1) Create a new node with the given value `val`.
2) Set the `next` pointer of the new node to point to the node that was originally the second node (i.e., the node after the head).
3) Update the `next` pointer of the head to point to the new node.
4) Return the head of the linked list.

⚠️ Common Mistakes

  • Forgetting to handle the case where the list contains only one node, leading to incorrect pointer assignments.
  • Not correctly updating the next pointers, causing incorrect list sequences.

4: I-mplement

Implement the code to solve the algorithm.

def add_second(head, val):
    # Create the new node that needs to be added
    new_node = Node(val)
    
    # Insert the new node as the second node
    new_node.next = head.next
    head.next = new_node
    
    # Return the unchanged head of the list
    return head

5: R-eview

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

  • Verify the order of nodes after insertion to ensure the linked list is correctly updated.

Example:

head = Node("banana")
head.next = Node("blue shell")
head.next.next = Node("bullet bill")

new_head = add_second(head, "red shell")
print_linked_list(new_head)
# Expected Output: "banana -> red shell -> blue shell -> bullet bill"

6: E-valuate

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

  • Time Complexity: O(1) for the insertion operation since we are directly updating the pointers.
  • Space Complexity: O(1) because we are only adding one new node.