LeetCode 707: Design Linked List Solution

Master LeetCode problem 707 (Design Linked List), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

707. Design Linked List

Medium

Linked List Design

Problem Explanation

Explanation

To implement a linked list, we can create a Node class to represent each node in the list. The Node class will have fields for the value of the node and a reference to the next node. We will also create a MyLinkedList class that will have methods to perform operations like getting a value at a specific index, adding a node at the head, tail, or at a specific index, and deleting a node at a specific index.

Algorithm:

Create a Node class with fields for value and next (and prev for doubly linked list).
Implement MyLinkedList class with the following methods:
- get(int index): Traverse the list to find the node at the given index.
- addAtHead(int val): Create a new node and update the head.
- addAtTail(int val): Traverse the list to find the last node and add a new node.
- addAtIndex(int index, int val): Traverse to the node at (index-1) and update its next pointer.
- deleteAtIndex(int index): Traverse to the node at (index-1), update its next pointer to skip the desired node.

Time Complexity:

get(int index): O(n)
addAtHead(int val): O(1)
addAtTail(int val): O(n)
addAtIndex(int index, int val): O(n)
deleteAtIndex(int index): O(n)

Space Complexity:

O(n) where n is the number of nodes in the linked list.

Solution Code

class Node {
    int val;
    Node next;
    
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {
    Node head;
    int size;

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

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

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

    public void addAtTail(int val) {
        if (head == null) {
            addAtHead(val);
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = new Node(val);
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addAtHead(val);
            return;
        }
        Node newNode = new Node(val);
        Node curr = head;
        for (int i = 0; i < index - 1; i++) {
            curr = curr.next;
        }
        newNode.next = curr.next;
        curr.next = newNode;
        size++;
    }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 707 (Design Linked List)?

This page provides optimized solutions for LeetCode problem 707 (Design Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 707 (Design Linked List)?

The time complexity for LeetCode 707 (Design Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 707 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 707 in Java, C++, or Python.

Back to LeetCode Solutions