Insert Value

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

U-nderstand

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

• What should the function do if the index i is out of the list's current bounds?
  • If i is beyond the current end of the list, the new node should be inserted at the end of the list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Insert a new node at the specified index in the linked list, handling edge cases where i is 0 or beyond the end of the list.

1) If the list is empty (`head` is `None`), create a new node with the value and return it as the new head.
2) If the index `i` is 0, insert the new node before the current head and return the new node as the new head.
3) Use a loop to find the correct position in the list where the new node should be inserted:
   a) Traverse the list until reaching the position just before the index `i`.
   b) Insert the new node at index `i` by adjusting the `next` pointers.
4) If `i` exceeds the length of the list, append the new node at the end.
5) Return the head of the list.

⚠️ Common Mistakes

• Failing to adjust the next pointers correctly, which could lead to losing part of the list.
• Not considering the case where i is greater than the number of nodes, which should not throw an error but append the node at the end.

I-mplement

def ll_insert(head, val, i):
  if not head:
    return Node(val)

  if i == 0:
    return Node(val, head)

  current = head
  count = 0
  while current:
      if i == count:
        new_node = Node(val)
        new_node.next = current.next
        current.next = new_node
        return head