Linked List (4) - Remove and Reverse

In my Python algorithms class, we recently worked with linked lists. The reverse method is a popular topic in technical interviews, but it was slightly harder to understand than the remove method. Below are detailed notes on both.

Remove

The remove method deletes a node at a specific index in the linked list.

def remove(self, index):
        if index < 0 or index >= self.length:
            return None
        if index == 0:
            return self.pop_first()
        if index == self.length - 1:
            return self.pop()
        pre = self.get(index - 1)
        temp = pre.next
        pre.next = temp.next
        temp.next = None
        self.length -= 1
        return temp

Bounds Check: Checks if the index is within the valid range (0 to self.length - 1). If not, it returns None.

• Edge Cases:

  • If index is 0: It removes the first node by calling pop_first.

  • If index is the last node: It removes the last node by calling pop.

• Removing a Middle Node:

  • Finds the node just before the target (pre) using self.get(index - 1).

  • Sets temp to pre.next, which is the node to be removed.

  • Updates pre.next to temp.next, effectively skipping over temp.

  • Disconnects temp by setting temp.next to None, decrements self.length, and returns temp.

---

Reverse

The reverse method reverses the order of nodes in the list.

def reverse(self):
        temp = self.head
        self.head = self.tail
        self.tail = temp
        after = temp.next
        before = None

        for _ in range(self.length):
            after = temp.next
            temp.next = before
            before = temp
            temp = after

Head and Tail Swap: Sets self.head to self.tail and vice versa, starting the reversal process.

• Three-Pointer Setup:

  • Initializes before, temp, and after pointers to track and reverse links.

  • before starts as None, temp is set to head, and after is temp.next.

• Reversing Links:

  • In a loop that runs self.length times:

    • Stores temp.next in after.

    • Reverses temp.next to point to before.

    • Advances before to temp and temp to after.Reverse the Links:

• Iterate over the list using a for loop that runs as long as the length of the linked list.

• Inside the loop:

  • Set after to temp.next, keeping track of the next node.

  • Reverse the link by setting temp.next to before.

  • Move before to temp, then advance temp to after.