• Difficulty: Easy

---

Problem Definition

Given a linked list and an index in the linked list, write a function to delete the given index from the linked list. Assume the index starts at 0 for the first item in the linked list.

---

Node Class

This is the class that represents each node in the linked list.

class Node:
    def __init__(self, val, nxt: 'Node' = None):
        self.val = val
        self.nxt = nxt

---

Examples

Some test cases to verify our solution.

# 0->1->2->3->4->5
root = Node(0, Node(1, Node(2, Node(3, Node(4, Node(5))))))
assert root.to_list() == [0, 1, 2, 3, 4, 5]
delete_index(root, 1)
# Should now be 0->2->3->4->5
assert root.to_list() == [0, 2, 3, 4, 5]
delete_index(root, 0)
# Should now be 2->3->4->5
assert root.to_list() == [2, 3, 4, 5]
delete_index(root, 3)
# Should now be 2->3->4
assert root.to_list() == [2, 3, 4]

---

Solution

We will maintain a counter as we traverse the linked list. Once we have hit our target idx, we will break out of the loop and remove the current Node from the linked list.

def delete_index(head: Node, idx: int):
    curr_idx = 0
    prev = None
    while curr_idx != idx and head is not None:
        prev = head
        head = head.nxt
        curr_idx += 1
    if curr_idx == idx:
        nxt = head.nxt
        prev.nxt = nxt
    else:
        raise IndexError(f"{idx} out of range, max length is {curr}.")

---

Complexity

Let $n =$ length of the linked list.

Since we are looking at each element once, the runtime complexity should be $O(n)$.

Auxiliary space complexity should be $O(1)$ since we are storing just a handful of temporary variables.