LeetCode Solutions Blog

Design Linked List

Difficulty: Medium

Problem Description

Design your implementation of the linked list. You can choose to use a singly or doubly linked list. Implement the MyLinkedList class with methods to get a node's value, add nodes at the head, tail, or at a specific index, and delete a node at a specific index.

Key Insights

A linked list consists of nodes where each node contains a value and a pointer to the next node.
Operations include adding, retrieving, and deleting nodes based on their index.
Edge cases such as invalid indices and operations on an empty list must be handled gracefully.

Space and Time Complexity

Time Complexity:

get: O(n) in the worst case (traversing the list)
addAtHead: O(1)
addAtTail: O(1)
addAtIndex: O(n) in the worst case (traversing to the index)
deleteAtIndex: O(n) in the worst case (traversing to the index)

Space Complexity: O(n) for storing the nodes in the linked list.

Solution

This problem can be solved using a singly linked list. Each node will contain a value and a pointer to the next node. The MyLinkedList class maintains a reference to the head of the list and the size of the list.

Adding Nodes: When adding at the head, a new node is created and the head reference is updated. For adding at the tail, we traverse to the end of the list and append the new node. When adding at a specific index, we check for the validity of the index and insert the node accordingly.
Retrieving Nodes: The get method traverses the list to return the value at the specified index or -1 if the index is invalid.
Deleting Nodes: The deleteAtIndex method checks if the index is valid and adjusts the pointers to remove the node from the list.

Code Solutions

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

class MyLinkedList:
    def __init__(self):
        self.head = None  # Initialize the head of the linked list
        self.size = 0  # Keep track of the size

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1  # Invalid index
        current = self.head
        for _ in range(index):
            current = current.next  # Traverse to the index
        return current.val  # Return the value at the index

    def addAtHead(self, val: int) -> None:
        newNode = Node(val)  # Create a new node
        newNode.next = self.head  # Point to the current head
        self.head = newNode  # Update head to new node
        self.size += 1  # Increase size

    def addAtTail(self, val: int) -> None:
        newNode = Node(val)  # Create a new node
        if not self.head:
            self.head = newNode  # If the list is empty, set new node as head
        else:
            current = self.head
            while current.next:  # Traverse to the end
                current = current.next
            current.next = newNode  # Link the new node
        self.size += 1  # Increase size

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return  # Invalid index
        if index == 0:
            self.addAtHead(val)  # If index is 0, add at head
        else:
            newNode = Node(val)
            current = self.head
            for _ in range(index - 1):  # Traverse to the node before the index
                current = current.next
            newNode.next = current.next  # Link new node
            current.next = newNode  # Insert new node
            self.size += 1  # Increase size

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return  # Invalid index
        if index == 0:
            self.head = self.head.next  # Update head if deleting the first node
        else:
            current = self.head
            for _ in range(index - 1):  # Traverse to the node before the index
                current = current.next
            current.next = current.next.next  # Bypass the node to delete
        self.size -= 1  # Decrease size