Introduction

In this blog post, we will explore how to solve the LeetCode problem "707" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Design your implementation of the linked list. You can choose to use a singly or doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. Implement the MyLinkedList class: MyLinkedList() Initializes the MyLinkedList object. int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1. void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. void addAtTail(int val) Append a node of value val as the last element of the linked list. void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted. void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid. Example 1: Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] Output [null, null, null, null, 2, null, 3] Explanation MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3 Constraints: 0 <= index, val <= 1000 Please do not use the built-in LinkedList library. At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Explanation

• Data Structure: Use a doubly linked list to facilitate efficient insertion and deletion at any index. Maintain a head and tail pointer for O(1) addition to the head and tail. Store the size of the list to prevent traversing to the end of the list for every size-related operation.
  • Index Handling: Implement helper functions to get the node at a given index. Optimize the search by starting from either the head or the tail depending on which is closer to the target index.
  • Edge Cases: Handle edge cases like empty lists and invalid indices gracefully, returning -1 for invalid get operations and doing nothing for invalid deleteAtIndex and addAtIndex operations.

• Runtime Complexity: O(n) for get, addAtIndex, and deleteAtIndex in the worst case (traversing the list). O(1) for addAtHead and addAtTail. Storage Complexity: O(n)

Code

    class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class MyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        if index < self.size // 2:
            curr = self.head
            for _ in range(index):
                curr = curr.next
        else:
            curr = self.tail
            for _ in range(self.size - 1 - index):
                curr = curr.prev

        return curr.val

    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return

        if index == 0:
            self.addAtHead(val)
            return

        if index == self.size:
            self.addAtTail(val)
            return

        new_node = Node(val)

        if index < self.size // 2:
            curr = self.head
            for _ in range(index):
                curr = curr.next
        else:
            curr = self.tail
            for _ in range(self.size - index):
                curr = curr.prev

        new_node.next = curr
        new_node.prev = curr.prev
        curr.prev.next = new_node
        curr.prev = new_node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        if self.size == 1:
            self.head = None
            self.tail = None
            self.size = 0
            return

        if index == 0:
            self.head = self.head.next
            self.head.prev = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            if index < self.size // 2:
                curr = self.head
                for _ in range(index):
                    curr = curr.next
            else:
                curr = self.tail
                for _ in range(self.size - 1 - index):
                    curr = curr.prev

            curr.prev.next = curr.next
            curr.next.prev = curr.prev
        self.size -= 1