算法题 设计链表

设计链表

问题描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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个节点

代码实现

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

classMyLinkedList{// 链表节点定义privatestaticclassListNode{intval;ListNodenext;ListNode(intval){this.val=val;this.next=null;}}privateListNodedummyHead;// 虚拟头节点privateintsize;// 链表长度/** * 初始化链表 */publicMyLinkedList(){dummyHead=newListNode(-1);// 虚拟头节点，值不重要size=0;}/** * 获取链表中第index个节点的值 * * @param index 节点索引 (0-based) * @return 节点值，如果索引无效返回-1 */publicintget(intindex){// 检查索引有效性if(index<0||index>=size){return-1;}// 从虚拟头节点开始，移动index+1步到达目标节点ListNodecurrent=dummyHead;for(inti=0;i<=index;i++){current=current.next;}returncurrent.val;}/** * 在链表头部添加节点 * * @param val 要添加的节点值 */publicvoidaddAtHead(intval){addAtIndex(0,val);}/** * 在链表尾部添加节点 * * @param val 要添加的节点值 */publicvoidaddAtTail(intval){addAtIndex(size,val);}/** * 在指定索引位置添加节点 * * @param index 插入位置的索引 * @param val 要添加的节点值 */publicvoidaddAtIndex(intindex,intval){// 如果index大于链表长度，不插入if(index>size){return;}// 如果index小于0，在头部插入if(index<0){index=0;}// 找到插入位置的前一个节点ListNodeprev=dummyHead;for(inti=0;i<index;i++){prev=prev.next;}// 创建新节点并插入ListNodenewNode=newListNode(val);newNode.next=prev.next;prev.next=newNode;size++;}/** * 删除指定索引位置的节点 * * @param index 要删除的节点索引 */publicvoiddeleteAtIndex(intindex){// 检查索引有效性if(index<0||index>=size){return;}// 找到要删除节点的前一个节点ListNodeprev=dummyHead;for(inti=0;i<index;i++){prev=prev.next;}// 删除节点prev.next=prev.next.next;size--;}}

方法二：双链表

classMyLinkedList{privatestaticclassListNode{intval;ListNodenext;ListNodeprev;ListNode(intval){this.val=val;}}privateListNodehead;// 虚拟头节点privateListNodetail;// 虚拟尾节点privateintsize;publicMyLinkedList(){head=newListNode(-1);tail=newListNode(-1);head.next=tail;tail.prev=head;size=0;}publicintget(intindex){if(index<0||index>=size){return-1;}ListNodecurrent;// 从较近的一端开始遍历if(index<size/2){current=head.next;for(inti=0;i<index;i++){current=current.next;}}else{current=tail.prev;for(inti=0;i<size-1-index;i++){current=current.prev;}}returncurrent.val;}publicvoidaddAtHead(intval){addAtIndex(0,val);}publicvoidaddAtTail(intval){addAtIndex(size,val);}publicvoidaddAtIndex(intindex,intval){if(index>size){return;}if(index<0){index=0;}ListNodeprev;if(index<size/2){prev=head;for(inti=0;i<index;i++){prev=prev.next;}}else{prev=tail.prev;for(inti=0;i<size-index;i++){prev=prev.prev;}}ListNodenewNode=newListNode(val);ListNodenext=prev.next;prev.next=newNode;newNode.prev=prev;newNode.next=next;next.prev=newNode;size++;}publicvoiddeleteAtIndex(intindex){if(index<0||index>=size){return;}ListNodecurrent;if(index<size/2){current=head.next;for(inti=0;i<index;i++){current=current.next;}}else{current=tail.prev;for(inti=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

测试用例

publicclassTestMyLinkedList{publicstaticvoidmain(String[]args){// 测试用例1：标准示例MyLinkedListmyLinkedList1=newMyLinkedList();myLinkedList1.addAtHead(1);// [1]myLinkedList1.addAtTail(3);// [1,3]myLinkedList1.addAtIndex(1,2);// [1,2,3]System.out.println("get(1): "+myLinkedList1.get(1));// 2myLinkedList1.deleteAtIndex(1);// [1,3]System.out.println("get(1): "+myLinkedList1.get(1));// 3System.out.println();// 测试用例2：边界索引MyLinkedListmyLinkedList2=newMyLinkedList();System.out.println("get(0): "+myLinkedList2.get(0));// -1 (空链表)myLinkedList2.addAtHead(1);System.out.println("get(0): "+myLinkedList2.get(0));// 1System.out.println("get(1): "+myLinkedList2.get(1));// -1 (越界)myLinkedList2.deleteAtIndex(0);// 删除唯一元素System.out.println("get(0): "+myLinkedList2.get(0));// -1System.out.println();// 测试用例3：addAtIndex边界情况MyLinkedListmyLinkedList3=newMyLinkedList();myLinkedList3.addAtIndex(0,1);// 等同于addAtHeadmyLinkedList3.addAtIndex(1,2);// 等同于addAtTailmyLinkedList3.addAtIndex(1,3);// 在中间插入// 链表: [1,3,2]System.out.println("get(0): "+myLinkedList3.get(0));// 1System.out.println("get(1): "+myLinkedList3.get(1));// 3System.out.println("get(2): "+myLinkedList3.get(2));// 2// 测试用例4：重复操作MyLinkedListmyLinkedList5=newMyLinkedList();myLinkedList5.addAtHead(1);myLinkedList5.addAtHead(1);// 允许重复值myLinkedList5.addAtTail(1);// 链表: [1,1,1]System.out.println("get(0): "+myLinkedList5.get(0));// 1System.out.println("get(1): "+myLinkedList5.get(1));// 1System.out.println("get(2): "+myLinkedList5.get(2));// 1myLinkedList5.deleteAtIndex(1);// 删除中间的1// 链表: [1,1]System.out.println("get(0): "+myLinkedList5.get(0));// 1System.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：在指定位置插入