707. Design Linked List - Leetcode Solution

Code Implementation

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

class MyLinkedList:

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

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        curr = self.head
        for _ in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val: int) -> None:
        node = ListNode(val, self.head)
        self.head = node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        node = ListNode(val)
        if not self.head:
            self.head = node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0:
            index = 0
        if index > self.size:
            return
        if index == 0:
            self.addAtHead(val)
        else:
            prev = self.head
            for _ in range(index - 1):
                prev = prev.next
            node = ListNode(val, prev.next)
            prev.next = node
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
        else:
            prev = self.head
            for _ in range(index - 1):
                prev = prev.next
            prev.next = prev.next.next
        self.size -= 1

class MyLinkedList {
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int v): val(v), next(nullptr) {}
    };
    ListNode* head;
    int size;
public:
    MyLinkedList() {
        head = nullptr;
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode* curr = head;
        for (int i = 0; i < index; ++i)
            curr = curr->next;
        return curr->val;
    }
    
    void addAtHead(int val) {
        ListNode* node = new ListNode(val);
        node->next = head;
        head = node;
        ++size;
    }
    
    void addAtTail(int val) {
        ListNode* node = new ListNode(val);
        if (!head) {
            head = node;
        } else {
            ListNode* curr = head;
            while (curr->next)
                curr = curr->next;
            curr->next = node;
        }
        ++size;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0) index = 0;
        if (index > size) return;
        if (index == 0) {
            addAtHead(val);
        } else {
            ListNode* prev = head;
            for (int i = 0; i < index - 1; ++i)
                prev = prev->next;
            ListNode* node = new ListNode(val);
            node->next = prev->next;
            prev->next = node;
            ++size;
        }
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        if (index == 0) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        } else {
            ListNode* prev = head;
            for (int i = 0; i < index - 1; ++i)
                prev = prev->next;
            ListNode* tmp = prev->next;
            prev->next = tmp->next;
            delete tmp;
        }
        --size;
    }
};

class MyLinkedList {
    private class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }
    private ListNode head;
    private int size;

    public MyLinkedList() {
        head = null;
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode curr = head;
        for (int i = 0; i < index; i++)
            curr = curr.next;
        return curr.val;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
        size++;
    }

    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = node;
        } else {
            ListNode curr = head;
            while (curr.next != null)
                curr = curr.next;
            curr.next = node;
        }
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0) index = 0;
        if (index > size) return;
        if (index == 0) {
            addAtHead(val);
        } else {
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++)
                prev = prev.next;
            ListNode node = new ListNode(val);
            node.next = prev.next;
            prev.next = node;
            size++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        if (index == 0) {
            head = head.next;
        } else {
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++)
                prev = prev.next;
            prev.next = prev.next.next;
        }
        size--;
    }
}

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    get(index) {
        if (index < 0 || index >= this.size) return -1;
        let curr = this.head;
        for (let i = 0; i < index; i++)
            curr = curr.next;
        return curr.val;
    }
    
    addAtHead(val) {
        const node = new ListNode(val, this.head);
        this.head = node;
        this.size++;
    }
    
    addAtTail(val) {
        const node = new ListNode(val);
        if (!this.head) {
            this.head = node;
        } else {
            let curr = this.head;
            while (curr.next)
                curr = curr.next;
            curr.next = node;
        }
        this.size++;
    }
    
    addAtIndex(index, val) {
        if (index < 0) index = 0;
        if (index > this.size) return;
        if (index === 0) {
            this.addAtHead(val);
        } else {
            let prev = this.head;
            for (let i = 0; i < index - 1; i++)
                prev = prev.next;
            const node = new ListNode(val, prev.next);
            prev.next = node;
            this.size++;
        }
    }
    
    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        if (index === 0) {
            this.head = this.head.next;
        } else {
            let prev = this.head;
            for (let i = 0; i < index - 1; i++)
                prev = prev.next;
            prev.next = prev.next.next;
        }
        this.size--;
    }
}

Problem Description

The "Design Linked List" problem requires you to implement a singly linked list data structure that supports several operations:

get(index): Retrieve the value of the node at the specified index. If the index is invalid, return -1.
addAtHead(val): Add a node of value val before the first node of the linked list. After the insertion, the new node will be the first node of the linked list.
addAtTail(val): Append a node of value val as the last node of the linked list.
addAtIndex(index, val): Add a node of value val before the index-th node in the linked list. If index equals the length of the list, the node will be appended to the end. If index is greater than the length, the node will not be inserted. If index is less than 0, the node will be inserted at the head.
deleteAtIndex(index): Delete the index-th node in the linked list, if the index is valid.

Key constraints:

All operations should be implemented efficiently for a singly linked list.
Each operation should handle edge cases, such as empty lists and invalid indices.
Only one valid solution is required, and you should not reuse or share node elements between different positions.

Thought Process

The core of this problem is to simulate a classic singly linked list and provide methods to manipulate it. At first, you might consider using a built-in list or array, but the challenge specifically asks for linked list behavior, especially for insertions and deletions at arbitrary positions, which are inefficient in arrays.

The brute-force approach could involve traversing the entire list for every operation, but this would be slow for large lists. Instead, we want to manage the head pointer and keep track of the list's size to make validations and insertions more efficient.

For each operation:

For get, we traverse from the head up to the indexth node.
For addAtHead and addAtTail, we handle the pointers directly at the start or end.
For addAtIndex and deleteAtIndex, we need to traverse to the node just before the desired position, then update pointers accordingly.

By maintaining a size variable, we can quickly check if an index is valid, making our implementation robust and efficient.

Solution Approach

Let's break down the solution step by step:

Node Structure:
- We define a ListNode class (or struct) with two fields: val for the value and next for the reference to the next node.
Linked List Class:
- We create a MyLinkedList class with a head pointer and a size integer to keep track of the number of nodes.
Get Operation:
- We check if the index is valid. If not, return -1.
- Otherwise, traverse from the head node, moving forward index times to reach the desired node, and return its value.
Add at Head:
- Create a new node, set its next to the current head, and update head to this new node. Increment size.
Add at Tail:
- If the list is empty, set head to the new node.
- Otherwise, traverse to the last node and set its next to the new node. Increment size.
Add at Index:
- If index is less than 0, treat it as 0 (insert at head).
- If index is greater than size, do nothing.
- If index is 0, call addAtHead.
- Otherwise, traverse to the node at index-1, insert the new node after it, and increment size.
Delete at Index:
- If index is invalid, do nothing.
- If index is 0, update head to head.next.
- Otherwise, traverse to the node at index-1, and update its next to skip the node at index. Decrement size.

Each operation is carefully designed to handle edge cases, such as empty lists or out-of-bounds indices, making the implementation robust and efficient.

Example Walkthrough

Let's walk through a sample sequence of operations:

Operations:

MyLinkedList() // initialize empty list
addAtHead(1) // list: 1
addAtTail(3) // list: 1 -> 3
addAtIndex(1, 2) // list: 1 -> 2 -> 3
get(1) // returns 2
deleteAtIndex(1) // list: 1 -> 3
get(1) // returns 3

Step-by-step:

Initialize: List is empty.
addAtHead(1): List becomes 1.
addAtTail(3): List becomes 1 -> 3.
addAtIndex(1, 2): Insert 2 before index 1. List becomes 1 -> 2 -> 3.
get(1): Traverse to index 1 (second node), value is 2.
deleteAtIndex(1): Remove node at index 1 (the node with value 2). List becomes 1 -> 3.
get(1): Traverse to index 1 (second node), value is 3.

Each operation modifies the list as expected, demonstrating the correctness of the implementation.

Time and Space Complexity

Brute-force Approach:

Without a linked list, using an array would make addAtHead, addAtIndex, and deleteAtIndex O(N) due to shifting elements.

Optimized Approach (Linked List):

get(index): O(N) because we may need to traverse up to N nodes.
addAtHead(val): O(1) because we only update the head pointer.
addAtTail(val): O(N) because we must traverse to the end (unless we keep a tail pointer).
addAtIndex(index, val): O(N) because we may need to traverse up to index-1 nodes.
deleteAtIndex(index): O(N) because we may need to traverse up to index-1 nodes.

Space Complexity:

O(N) for storing N nodes in the list.

The approach is efficient for a linked list, as each node only stores a value and a pointer, and operations do not require extra space beyond the list itself.

Summary

In summary, the "Design Linked List" problem challenges you to implement a singly linked list with basic operations. The key is to manage node pointers and a size variable to ensure robust and efficient handling of insertions, deletions, and retrievals. Each operation is carefully crafted to traverse the list only as much as necessary, and edge cases are handled gracefully. The elegance of this solution lies in its simplicity and direct mapping to the fundamental principles of linked lists, making it a great exercise for mastering data structure implementation.

AlgoMap.io

Want Help Cracking FAANG?