707. Design Linked List

MediumView on LeetCode

Linked List Design

Time: O(n)

Space: O(n)

Intuition

Implement singly or doubly linked list with a dummy head for easier insertions/deletions.

Algorithm

1Maintain dummy head node and size.
2get(index): traverse from head to index.
3addAtHead/addAtTail: special cases of addAtIndex.
4addAtIndex(i,val): traverse to node before i, insert.
5deleteAtIndex(i): traverse to node before i, skip the target.

Common Pitfalls

•Always validate index bounds. Doubly linked list makes deleteAtIndex and addAtTail O(1) with tail pointer.

707.cs

// Approach: Singly-linked list with a dummy head node; maintain length for
// O(1) index validation and O(n) traversal.
// Time: O(n) Space: O(n)

public class MyLinkedList
{

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

    private int length = 0;
    private ListNode dummy = new ListNode(0);

    public MyLinkedList()
    {

    }

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

    public void AddAtHead(int val)
    {
        ListNode head = dummy.next;
        ListNode node = new ListNode(val);
        node.next = head;
        dummy.next = node;
        ++length;
    }

    public void AddAtTail(int val)
    {
        ListNode curr = dummy;
        while (curr.next != null)
            curr = curr.next;
        curr.next = new ListNode(val);
        ++length;
    }

    public void AddAtIndex(int index, int val)
    {
        if (index > length)
            return;
        ListNode curr = dummy;
        for (int i = 0; i < index; ++i)
            curr = curr.next;
        ListNode cache = curr.next;
        ListNode node = new ListNode(val);
        node.next = cache;
        curr.next = node;
        ++length;
    }

    public void DeleteAtIndex(int index)
    {
        if (index < 0 || index >= length)
            return;
        ListNode curr = dummy;
        for (int i = 0; i < index; ++i)
            curr = curr.next;
        ListNode cache = curr.next;
        curr.next = cache.next;
        --length;
    }
}

Was this solution helpful?