設計一個鏈結串列的實作。可以選擇單向或雙向鏈結串列。實作
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
TIP
核心思路：使用 dummy head（和 dummy tail）簡化邊界處理，維護 size 追蹤長度。
- 單向鏈結串列實作較簡單但某些操作需要找前一個節點
- 雙向鏈結串列可以從兩端遍歷，對靠近尾部的操作更高效
- Dummy 節點避免了插入/刪除頭尾時的特殊處理
Approaches
1. Singly Linked List — O(n) / O(n)
- Idea: 使用 dummy head 和 size，所有操作先定位到目標節點的前一個節點
- Time:
O(n)- get/add/delete 最差需遍歷整個串列 - Space:
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 — O(n) / O(n)
- Idea: 使用 dummy head 和 dummy tail，可以從兩端遍歷，靠近尾部的操作更快
- Time:
O(n)- 最差 O(n/2)，因為可從較近的一端遍歷 - Space:
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: 這是鏈結串列基礎操作的綜合練習，掌握後能更好理解其他鏈結串列題目
- Key trick: Dummy head/tail 消除邊界條件；維護 size 變數可以快速做 index 合法性檢查和雙向遍歷的方向選擇