Design Linked List

Problem

Design a singly linked list MyLinkedList with get(int index), addAtHead(int val), addAtTail(int val), addAtIndex(int index, int val), and deleteAtIndex(int index).

Constraints

• 0 ≤ index, val ≤ 1000

Approach — Linked List

This is a Linked List problem. The idea: rework the list with careful pointer manipulation — often a dummy head and fast/slow pointers — in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) space.

Solution code

Python

class MyLinkedList:

    def __init__(self):
        self.dummy = [None, None]  # [value, next]
        self.size = 0

    def get(self, index):
        if index < 0 or index >= self.size:
            return -1
        cur = self.dummy[1]
        for _ in range(index):
            cur = cur[1]
        return cur[0]

    def addAtHead(self, val):
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev[1]
        prev[1] = [val, prev[1]]
        self.size += 1

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev[1]
        prev[1] = prev[1][1]
        self.size -= 1

Java

class MyLinkedList {
    private static class Node {
        int val; Node next;
        Node(int v) { val = v; }
    }
    private Node dummy = new Node(0);
    private int size = 0;
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node cur = dummy.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }
    public void addAtHead(int val) { addAtIndex(0, val); }
    public void addAtTail(int val) { addAtIndex(size, val); }
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) prev = prev.next;
        Node n = new Node(val);
        n.next = prev.next;
        prev.next = n;
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = prev.next.next;
        size--;
    }
}

class Solution {}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.