设计链表

问题描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。

实现 MyLinkedList 类：

• int get(int index) 获取链表中第 index 个节点的值。如果索引无效，则返回 -1。
• void addAtHead(int val) 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• void addAtTail(int val) 将值为 val 的节点追加到链表的最后一个元素。
• void addAtIndex(int index, int val) 在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于 0，则在头部插入节点。
• void deleteAtIndex(int index) 如果索引 index 有效，则删除链表中的第 index 个节点。

注意：

• 所有 val 值都在 [1, 1000] 范围内。
• 操作次数不会超过 2000 次。
• 请不要使用内置的 LinkedList 库。

示例：

输入: ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
      [[], [1], [3], [1,2], [1], [1], [1]]
输出: [null, null, null, null, 2, null, 3]

解释:
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);    // 链表: 1
myLinkedList.addAtTail(3);    // 链表: 1->3
myLinkedList.addAtIndex(1,2); // 链表: 1->2->3
myLinkedList.get(1);          // 返回 2
myLinkedList.deleteAtIndex(1); // 链表: 1->3
myLinkedList.get(1);          // 返回 3

算法思路

1. 虚拟头节点（哨兵节点）：

   • 使用虚拟头节点简化边界处理
   • 避免对空链表的特殊处理
   • 所有操作都可以统一处理

2. 长度维护：

   • 维护链表长度，避免每次遍历计算
   • 用于快速验证索引有效性

3. 操作：

   • get(index)：遍历到第index个节点
   • addAtHead(val)：在虚拟头节点后插入
   • addAtTail(val)：遍历到尾节点后插入
   • addAtIndex(index, val)：在第index个位置前插入
   • deleteAtIndex(index)：删除第index个节点

代码实现

方法一：单链表 + 虚拟头节点

class MyLinkedList {
    // 链表节点定义
    private static class ListNode {
        int val;
        ListNode next;
        
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    
    private ListNode dummyHead; // 虚拟头节点
    private int size;           // 链表长度
    
    /**
     * 初始化链表
     */
    public MyLinkedList() {
        dummyHead = new ListNode(-1); // 虚拟头节点，值不重要
        size = 0;
    }
    
    /**
     * 获取链表中第index个节点的值
     * 
     * @param index 节点索引 (0-based)
     * @return 节点值，如果索引无效返回-1
     */
    public int get(int index) {
        // 检查索引有效性
        if (index < 0 || index >= size) {
            return -1;
        }
        
        // 从虚拟头节点开始，移动index+1步到达目标节点
        ListNode current = dummyHead;
        for (int i = 0; i <= index; i++) {
            current = current.next;
        }
        
        return current.val;
    }
    
    /**
     * 在链表头部添加节点
     * 
     * @param val 要添加的节点值
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    /**
     * 在链表尾部添加节点
     * 
     * @param val 要添加的节点值
     */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    /**
     * 在指定索引位置添加节点
     * 
     * @param index 插入位置的索引
     * @param val 要添加的节点值
     */
    public void addAtIndex(int index, int val) {
        // 如果index大于链表长度，不插入
        if (index > size) {
            return;
        }
        
        // 如果index小于0，在头部插入
        if (index < 0) {
            index = 0;
        }
        
        // 找到插入位置的前一个节点
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        
        // 创建新节点并插入
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        
        size++;
    }
    
    /**
     * 删除指定索引位置的节点
     * 
     * @param index 要删除的节点索引
     */
    public void deleteAtIndex(int index) {
        // 检查索引有效性
        if (index < 0 || index >= size) {
            return;
        }
        
        // 找到要删除节点的前一个节点
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        
        // 删除节点
        prev.next = prev.next.next;
        
        size--;
    }
}

方法二：双链表

class MyLinkedList {
    private static class ListNode {
        int val;
        ListNode next;
        ListNode prev;
        
        ListNode(int val) {
            this.val = val;
        }
    }
    
    private ListNode head; // 虚拟头节点
    private ListNode tail; // 虚拟尾节点
    private int size;
    
    public MyLinkedList() {
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        
        ListNode current;
        // 从较近的一端开始遍历
        if (index < size / 2) {
            current = head.next;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            current = tail.prev;
            for (int i = 0; i < size - 1 - index; i++) {
                current = current.prev;
            }
        }
        
        return current.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        
        ListNode prev;
        if (index < size / 2) {
            prev = head;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
        } else {
            prev = tail.prev;
            for (int i = 0; i < size - index; i++) {
                prev = prev.prev;
            }
        }
        
        ListNode newNode = new ListNode(val);
        ListNode next = prev.next;
        
        prev.next = newNode;
        newNode.prev = prev;
        newNode.next = next;
        next.prev = newNode;
        
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        
        ListNode current;
        if (index < size / 2) {
            current = head.next;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            current = tail.prev;
            for (int i = 0; i < size - 1 - index; i++) {
                current = current.prev;
            }
        }
        
        current.prev.next = current.next;
        current.next.prev = current.prev;
        size--;
    }
}

算法分析

• 时间复杂度：
  • get(index)：O(index)，最坏O(n)
  • addAtHead(val)：O(1)
  • addAtTail(val)：O(n)（单链表），O(1)（双链表）
  • addAtIndex(index, val)：O(index)，最坏O(n)
  • deleteAtIndex(index)：O(index)，最坏O(n)
• 空间复杂度：O(n)，n为链表长度

算法过程

初始化：

• dummyHead → null
• size = 0

addAtHead(1)：

• 在dummyHead后插入1
• dummyHead → 1 → null
• size = 1

addAtTail(3)：

• 在尾部插入3
• dummyHead → 1 → 3 → null
• size = 2

addAtIndex(1, 2)：

• 在索引1位置插入2
• 找到索引0的节点（值为1）
• 插入2：dummyHead → 1 → 2 → 3 → null
• size = 3

get(1)：

• 返回索引1的值：2

deleteAtIndex(1)：

• 删除索引1的节点
• dummyHead → 1 → 3 → null
• size = 2

get(1)：

• 返回索引1的值：3

测试用例

public class TestMyLinkedList {
    public static void main(String[] args) {
        // 测试用例1：标准示例
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addAtHead(1);    // [1]
        myLinkedList1.addAtTail(3);    // [1,3]
        myLinkedList1.addAtIndex(1,2); // [1,2,3]
        System.out.println("get(1): " + myLinkedList1.get(1)); // 2
        myLinkedList1.deleteAtIndex(1); // [1,3]
        System.out.println("get(1): " + myLinkedList1.get(1)); // 3
        
        System.out.println();
        
        // 测试用例2：边界索引
        MyLinkedList myLinkedList2 = new MyLinkedList();
        System.out.println("get(0): " + myLinkedList2.get(0)); // -1 (空链表)
        myLinkedList2.addAtHead(1);
        System.out.println("get(0): " + myLinkedList2.get(0)); // 1
        System.out.println("get(1): " + myLinkedList2.get(1)); // -1 (越界)
        myLinkedList2.deleteAtIndex(0); // 删除唯一元素
        System.out.println("get(0): " + myLinkedList2.get(0)); // -1
        
        System.out.println();
        
        // 测试用例3：addAtIndex边界情况
        MyLinkedList myLinkedList3 = new MyLinkedList();
        myLinkedList3.addAtIndex(0, 1); // 等同于addAtHead
        myLinkedList3.addAtIndex(1, 2); // 等同于addAtTail
        myLinkedList3.addAtIndex(1, 3); // 在中间插入
        // 链表: [1,3,2]
        System.out.println("get(0): " + myLinkedList3.get(0)); // 1
        System.out.println("get(1): " + myLinkedList3.get(1)); // 3
        System.out.println("get(2): " + myLinkedList3.get(2)); // 2
        
        
        // 测试用例4：重复操作
        MyLinkedList myLinkedList5 = new MyLinkedList();
        myLinkedList5.addAtHead(1);
        myLinkedList5.addAtHead(1); // 允许重复值
        myLinkedList5.addAtTail(1);
        // 链表: [1,1,1]
        
        System.out.println("get(0): " + myLinkedList5.get(0)); // 1
        System.out.println("get(1): " + myLinkedList5.get(1)); // 1
        System.out.println("get(2): " + myLinkedList5.get(2)); // 1
        
        myLinkedList5.deleteAtIndex(1); // 删除中间的1
        // 链表: [1,1]
        System.out.println("get(0): " + myLinkedList5.get(0)); // 1
        System.out.println("get(1): " + myLinkedList5.get(1)); // 1
    }
   
}

关键点

1. 虚拟头节点：

   • 统一处理空链表和非空链表的情况
   • 避免对head的特殊处理
   • 简化插入和删除操作的代码

2. 索引有效性：

   • get和deleteAtIndex：索引范围 [0, size-1]
   • addAtIndex：索引范围 (-∞, size]，超出范围不插入

3. 复用：

   • addAtHead和addAtTail可以复用addAtIndex
   • 减少代码重复，提高可维护性

4. 边界情况处理：

   • 空链表的操作
   • 单节点链表的删除
   • 越界索引

常见问题

1. 为什么使用虚拟头节点？

   • 避免对空链表的特殊处理
   • 所有插入操作都可以统一为"在某节点后插入"
   • 删除操作总是有前驱节点，无需特殊处理头节点

2. addAtIndex的索引规则？

   • index < 0：在头部插入
   • index == size：在尾部插入
   • index > size：不插入
   • 0 <= index < size：在指定位置插入