algoadvance

Leetcode 707. Design Linked List

Problem Statement

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

Implement the MyLinkedList class:

Clarifying Questions

  1. Should we consider an empty linked list as valid during initialization?
  2. Can we assume that the values are all valid integers, including negative values?
  3. Should the addAtIndex and deleteAtIndex methods handle negative indices?

Code

We’ll implement a singly linked list using the given specifications.

public class MyLinkedList {
    // Basic structure for a node in singly linked list
    private class Node {
        int val;
        Node next;
        Node(int val) {
            this.val = val;
            this.next = null;
        }
    }
    
    private Node head;  // Points to the head (first node) of the list
    private int size;   // Tracks the size of the linked list

    public MyLinkedList() {
        head = null;
        size = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;  // Invalid index
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }
    
    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    public void addAtTail(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) return;  // Out of bounds
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        if (index == size) {
            addAtTail(val);
            return;
        }
        Node newNode = new Node(val);
        Node current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return; // Invalid index
        if (index == 0) {
            head = head.next;
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        size--;
    }
}

Strategy

  1. Initialization: Initialize an empty linked list with the head pointer null and size set to zero.
  2. Get: Traverse to the node at the specified index and return its value.
  3. Add at Head: Create a new node, set its next pointer to the current head, and update the head to this new node.
  4. Add at Tail: Traverse to the end of the list and append the new node.
  5. Add at Index: Traverse to the node just before the specified index and insert the new node. Handle boundary conditions for head and tail insertions.
  6. Delete at Index: Traverse to the node just before the specified index and adjust pointers to exclude the node at the target index.

Time Complexity

  1. Initialization: O(1)
  2. Get: O(n), where n is the index specified.
  3. Add at Head: O(1)
  4. Add at Tail: O(n) in the worst case.
  5. Add at Index: O(n) in the worst case.
  6. Delete at Index: O(n) in the worst case.

By implementing solutions based on these strategies, we can efficiently solve the problem of managing a custom linked list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI