707. Design Linked List

Medium

Description

設計一個鏈結串列的實作。可以選擇單向或雙向鏈結串列。實作 MyLinkedList 類別：get(index) 取得第 index 個節點的值、addAtHead(val) 在頭部新增、addAtTail(val) 在尾部新增、addAtIndex(index, val) 在第 index 個節點前插入、deleteAtIndex(index) 刪除第 index 個節點。

Example:

Input: [“MyLinkedList”,“addAtHead”,“addAtTail”,“addAtIndex”,“get”,“deleteAtIndex”,“get”], [[],[1],[3],[1,2],[1],[1],[1]] Output: [null,null,null,null,2,null,3]

Intuition#

核心思路：使用 dummy head（和 dummy tail）簡化邊界處理，維護 size 追蹤長度。

單向鏈結串列實作較簡單但某些操作需要找前一個節點
雙向鏈結串列可以從兩端遍歷，對靠近尾部的操作更高效
Dummy 節點避免了插入/刪除頭尾時的特殊處理

Approaches#

1: Singly Linked List#

概念: 使用 dummy head 和 size，所有操作先定位到目標節點的前一個節點
時間複雜度: O(n) - get/add/delete 最差需遍歷整個串列
空間複雜度: O(n)

class MyLinkedList() {

    private class Node(val `val`: Int, var next: Node? = null)

    private val dummy = Node(0)
    private var size = 0

    fun get(index: Int): Int {
        if (index < 0 || index >= size) return -1
        var curr = dummy.next
        for (i in 0 until index) {
            curr = curr?.next
        }
        return curr!!.`val`
    }

    fun addAtHead(`val`: Int) {
        addAtIndex(0, `val`)
    }

    fun addAtTail(`val`: Int) {
        addAtIndex(size, `val`)
    }

    fun addAtIndex(index: Int, `val`: Int) {
        if (index < 0 || index > size) return
        var prev = dummy
        for (i in 0 until index) {
            prev = prev.next!!
        }
        val node = Node(`val`)
        node.next = prev.next
        prev.next = node
        size++
    }

    fun deleteAtIndex(index: Int) {
        if (index < 0 || index >= size) return
        var prev = dummy
        for (i in 0 until index) {
            prev = prev.next!!
        }
        prev.next = prev.next?.next
        size--
    }
}

⭐2: Doubly Linked List#

概念: 使用 dummy head 和 dummy tail，可以從兩端遍歷，靠近尾部的操作更快
時間複雜度: O(n) - 最差 O(n/2)，因為可從較近的一端遍歷
空間複雜度: O(n)

class MyLinkedList() {

    private class Node(val `val`: Int) {
        var prev: Node? = null
        var next: Node? = null
    }

    private val head = Node(0) // dummy head
    private val tail = Node(0) // dummy tail
    private var size = 0

    init {
        head.next = tail
        tail.prev = head
    }

    private fun getNode(index: Int): Node {
        var curr: Node
        if (index < size / 2) {
            curr = head.next!!
            for (i in 0 until index) curr = curr.next!!
        } else {
            curr = tail.prev!!
            for (i in 0 until size - 1 - index) curr = curr.prev!!
        }
        return curr
    }

    fun get(index: Int): Int {
        if (index < 0 || index >= size) return -1
        return getNode(index).`val`
    }

    fun addAtHead(`val`: Int) {
        addAtIndex(0, `val`)
    }

    fun addAtTail(`val`: Int) {
        addAtIndex(size, `val`)
    }

    fun addAtIndex(index: Int, `val`: Int) {
        if (index < 0 || index > size) return
        val succ = if (index == size) tail else getNode(index)
        val pred = succ.prev!!
        val node = Node(`val`)
        node.prev = pred
        node.next = succ
        pred.next = node
        succ.prev = node
        size++
    }

    fun deleteAtIndex(index: Int) {
        if (index < 0 || index >= size) return
        val node = getNode(index)
        node.prev!!.next = node.next
        node.next!!.prev = node.prev
        size--
    }
}

🔑 Takeaways#

Pattern: 這是鏈結串列基礎操作的綜合練習，掌握後能更好理解其他鏈結串列題目
關鍵技巧: Dummy head/tail 消除邊界條件；維護 size 變數可以快速做 index 合法性檢查和雙向遍歷的方向選擇