设计链表完整实现详解

目录

概述

设计链表是数据结构学习中的经典题目,它要求我们实现一个完整的链表类,包含增删改查等基本操作。这道题不仅考察了链表的基本操作,还涉及虚拟头节点、单链表与双链表的选择等核心概念。通过这道题,我们可以深入理解链表的本质和实现技巧。

题目分析

题目要求

实现 MyLinkedList 类,包含以下五个核心方法:

  1. get(index) - 获取第index个节点的值
  2. addAtHead(val) - 在链表头部插入节点
  3. addAtTail(val) - 在链表尾部插入节点
  4. addAtIndex(index, val) - 在指定位置插入节点
  5. deleteAtIndex(index) - 删除指定位置的节点

关键挑战

  1. 边界条件处理:索引越界、空链表等
  2. 头节点特殊处理:插入/删除头节点需要特殊逻辑
  3. 性能优化:选择合适的链表类型和遍历策略
  4. 内存管理:正确释放被删除节点的内存

单链表实现

核心思想

使用虚拟头节点统一所有操作,避免头节点的特殊处理。

数据结构设计

struct LinkedNode {
    int val;                    // 节点值
    LinkedNode* next;           // 指向下一个节点的指针
    LinkedNode(int val):val(val), next(nullptr){}  // 构造函数
};

完整实现(C++)

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;                // 节点存储的值
        LinkedNode* next;       // 指向下一个节点的指针
        LinkedNode(int val):val(val), next(nullptr){}  // 构造函数
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);  // 创建虚拟头节点,值为0
        _size = 0;                       // 初始化链表大小为0
    }

    // 获取第index个节点的值
    int get(int index) {
        // 边界检查:索引无效返回-1
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        
        LinkedNode* cur = _dummyHead->next;  // 从第一个真实节点开始
        while(index--) {                     // 移动到目标位置
            cur = cur->next;
        }
        return cur->val;                     // 返回节点值
    }

    // 在链表头部插入节点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);  // 创建新节点
        newNode->next = _dummyHead->next;          // 新节点指向原头节点
        _dummyHead->next = newNode;                // 虚拟头节点指向新节点
        _size++;                                   // 链表大小加1
    }

    // 在链表尾部插入节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);  // 创建新节点
        LinkedNode* cur = _dummyHead;               // 从虚拟头节点开始
        while(cur->next != nullptr) {               // 找到最后一个节点
            cur = cur->next;
        }
        cur->next = newNode;                        // 在尾部插入新节点
        _size++;                                    // 链表大小加1
    }

    // 在指定位置插入节点
    void addAtIndex(int index, int val) {
        // 边界检查
        if(index > _size) return;                   // 索引超出范围
        if(index < 0) index = 0;                    // 负数索引视为0
        
        LinkedNode* newNode = new LinkedNode(val);  // 创建新节点
        LinkedNode* cur = _dummyHead;               // 从虚拟头节点开始
        while(index--) {                            // 移动到插入位置的前一个节点
            cur = cur->next;
        }
        newNode->next = cur->next;                  // 新节点指向下一个节点
        cur->next = newNode;                        // 前一个节点指向新节点
        _size++;                                    // 链表大小加1
    }

    // 删除指定位置的节点
    void deleteAtIndex(int index) {
        // 边界检查
        if (index >= _size || index < 0) {
            return;
        }
        
        LinkedNode* cur = _dummyHead;               // 从虚拟头节点开始
        while(index--) {                            // 移动到删除位置的前一个节点
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;                // 保存要删除的节点
        cur->next = cur->next->next;                // 跳过要删除的节点
        delete tmp;                                 // 释放内存
        tmp = nullptr;                              // 避免野指针
        _size--;                                    // 链表大小减1
    }

    // 打印链表(调试用)
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

private:
    int _size;                     // 链表大小
    LinkedNode* _dummyHead;        // 虚拟头节点
};

图示说明

虚拟头节点的作用:

原始链表:1 -> 2 -> 3 -> null
添加虚拟头节点:dummy -> 1 -> 2 -> 3 -> null
                ↑
              虚拟头节点

插入操作示例:

在头部插入0:
dummy -> 0 -> 1 -> 2 -> 3 -> null

在位置1插入5:
dummy -> 0 -> 5 -> 1 -> 2 -> 3 -> null

双链表实现

核心思想

使用循环虚拟节点(哨兵节点),支持双向遍历,提高查找效率。

数据结构设计

struct DList {
    int elem;           // 节点值
    DList *next;        // 指向下一个节点
    DList *prev;        // 指向上一个节点
    DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {};
};

完整实现(C++)

class MyLinkedList {
public:
    // 定义双向链表节点结构体
    struct DList {
        int elem;                           // 节点存储的元素
        DList *next;                        // 指向下一个节点的指针
        DList *prev;                        // 指向上一个节点的指针
        DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {};  // 构造函数
    };

    // 构造函数,初始化链表
    MyLinkedList() {
        sentinelNode = new DList(0);        // 创建哨兵节点
        sentinelNode->next = sentinelNode;  // 哨兵节点指向自身,形成循环
        sentinelNode->prev = sentinelNode;  // 哨兵节点指向自身,形成循环
        size = 0;                           // 初始化链表大小为0
    }

    // 获取第index个节点的值
    int get(int index) {
        if (index > (size - 1) || index < 0) {  // 边界检查
            return -1;
        }
        
        int mid = size >> 1;                // 计算链表中部位置
        DList *curNode = sentinelNode;      // 从哨兵节点开始
        
        if (index < mid) {                  // 从前半部分查找
            for (int i = 0; i < index + 1; i++) {
                curNode = curNode->next;
            }
        } else {                            // 从后半部分查找
            for (int i = 0; i < size - index; i++) {
                curNode = curNode->prev;
            }
        }
        return curNode->elem;               // 返回节点值
    }

    // 在链表头部添加节点
    void addAtHead(int val) {
        DList *newNode = new DList(val);    // 创建新节点
        DList *next = sentinelNode->next;   // 获取当前头节点
        
        newNode->prev = sentinelNode;       // 新节点的前驱指向哨兵节点
        newNode->next = next;               // 新节点的后继指向原头节点
        sentinelNode->next = newNode;       // 哨兵节点的后继指向新节点
        next->prev = newNode;               // 原头节点的前驱指向新节点
        size++;                             // 链表大小加1
    }

    // 在链表尾部添加节点
    void addAtTail(int val) {
        DList *newNode = new DList(val);    // 创建新节点
        DList *prev = sentinelNode->prev;   // 获取当前尾节点
        
        newNode->next = sentinelNode;       // 新节点的后继指向哨兵节点
        newNode->prev = prev;               // 新节点的前驱指向原尾节点
        sentinelNode->prev = newNode;       // 哨兵节点的前驱指向新节点
        prev->next = newNode;               // 原尾节点的后继指向新节点
        size++;                             // 链表大小加1
    }

    // 在指定位置插入节点
    void addAtIndex(int index, int val) {
        if (index > size) return;           // 边界检查
        if (index <= 0) {                   // 在头部插入
            addAtHead(val);
            return;
        }
        
        int mid = size >> 1;                // 计算链表中部位置
        DList *curNode = sentinelNode;      // 从哨兵节点开始
        
        if (index < mid) {                  // 从前半部分查找插入位置
            for (int i = 0; i < index; i++) {
                curNode = curNode->next;
            }
            DList *temp = curNode->next;    // 目标位置的节点
            DList *newNode = new DList(val); // 创建新节点
            
            curNode->next = newNode;        // 插入新节点
            temp->prev = newNode;
            newNode->next = temp;
            newNode->prev = curNode;
        } else {                            // 从后半部分查找插入位置
            for (int i = 0; i < size - index; i++) {
                curNode = curNode->prev;
            }
            DList *temp = curNode->prev;    // 目标位置的节点
            DList *newNode = new DList(val); // 创建新节点
            
            curNode->prev = newNode;        // 插入新节点
            temp->next = newNode;
            newNode->prev = temp;
            newNode->next = curNode;
        }
        size++;                             // 链表大小加1
    }

    // 删除指定位置的节点
    void deleteAtIndex(int index) {
        if (index > (size - 1) || index < 0) {  // 边界检查
            return;
        }
        
        int mid = size >> 1;                // 计算链表中部位置
        DList *curNode = sentinelNode;      // 从哨兵节点开始
        
        if (index < mid) {                  // 从前半部分查找删除位置
            for (int i = 0; i < index; i++) {
                curNode = curNode->next;
            }
            DList *next = curNode->next->next;  // 目标位置的下一个节点
            curNode->next = next;               // 删除目标节点
            next->prev = curNode;
        } else {                            // 从后半部分查找删除位置
            for (int i = 0; i < size - index - 1; i++) {
                curNode = curNode->prev;
            }
            DList *prev = curNode->prev->prev;  // 目标位置的上一个节点
            curNode->prev = prev;               // 删除目标节点
            prev->next = curNode;
        }
        size--;                             // 链表大小减1
    }

private:
    int size;                               // 链表大小
    DList *sentinelNode;                    // 哨兵节点
};

图示说明

循环双链表结构:

哨兵节点 <-> 节点1 <-> 节点2 <-> 节点3 <-> 哨兵节点
   ↑                                           ↑
   └─────────────── 循环连接 ──────────────────┘

双向遍历优化:

查找第2个节点(总共5个节点):
- 从前向后:需要2步
- 从后向前:需要2步
选择更短的路径

虚拟头节点的必要性

问题分析

不使用虚拟头节点的问题:

// 需要特殊处理头节点
if (head == nullptr) {
    head = new ListNode(val);
} else {
    // 插入逻辑
}

使用虚拟头节点的优势:

// 统一处理所有节点
dummy->next = newNode;
newNode->next = cur->next;
cur->next = newNode;

核心作用

  1. 统一操作逻辑:所有节点都可以用相同的插入/删除逻辑
  2. 简化边界条件:不需要特殊处理头节点为空的情况
  3. 提高代码健壮性:避免头节点相关的边界错误
  4. 增强可读性:代码逻辑更加清晰

图示对比

不使用虚拟头节点:

原始链表:1 -> 2 -> 3
插入头节点需要特殊处理:
新节点 -> 1 -> 2 -> 3

使用虚拟头节点:

虚拟头节点 -> 1 -> 2 -> 3
插入操作统一:
虚拟头节点 -> 新节点 -> 1 -> 2 -> 3

单链表与双链表的对比

性能对比

操作单链表双链表
查找O(n)O(n/2)
插入O(n)O(n/2)
删除O(n)O(n/2)
空间复杂度O(n)O(n)
实现复杂度简单复杂

适用场景

单链表适合:

  • 简单的线性操作
  • 内存使用要求严格
  • 实现简单性要求高

双链表适合:

  • 需要频繁的随机访问
  • 需要双向遍历
  • 性能要求较高

选择建议

  1. 一般情况:选择单链表,实现简单
  2. 性能要求高:选择双链表
  3. 内存受限:选择单链表
  4. 需要双向操作:选择双链表

C++实现详解

内存管理要点

// 正确的内存释放
void deleteAtIndex(int index) {
    // ... 查找逻辑 ...
    LinkedNode* tmp = cur->next;    // 保存要删除的节点
    cur->next = cur->next->next;    // 跳过要删除的节点
    delete tmp;                     // 释放内存
    tmp = nullptr;                  // 避免野指针
}

边界条件处理

// 完整的边界检查
int get(int index) {
    if (index > (_size - 1) || index < 0) {  // 检查索引范围
        return -1;
    }
    // ... 查找逻辑 ...
}

Python实现详解

单链表实现(Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val          # 节点值
        self.next = next        # 指向下一个节点的引用
        
class MyLinkedList:
    def __init__(self):
        self.dummy_head = ListNode()  # 创建虚拟头节点
        self.size = 0                 # 初始化链表大小

    def get(self, index: int) -> int:
        # 边界检查
        if index < 0 or index >= self.size:
            return -1
        
        current = self.dummy_head.next  # 从第一个真实节点开始
        for i in range(index):          # 移动到目标位置
            current = current.next
            
        return current.val              # 返回节点值

    def addAtHead(self, val: int) -> None:
        # 在虚拟头节点后插入新节点
        self.dummy_head.next = ListNode(val, self.dummy_head.next)
        self.size += 1                  # 链表大小加1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head       # 从虚拟头节点开始
        while current.next:             # 找到最后一个节点
            current = current.next
        current.next = ListNode(val)    # 在尾部插入新节点
        self.size += 1                  # 链表大小加1

    def addAtIndex(self, index: int, val: int) -> None:
        # 边界检查
        if index < 0 or index > self.size:
            return
        
        current = self.dummy_head       # 从虚拟头节点开始
        for i in range(index):          # 移动到插入位置的前一个节点
            current = current.next
        # 插入新节点
        current.next = ListNode(val, current.next)
        self.size += 1                  # 链表大小加1

    def deleteAtIndex(self, index: int) -> None:
        # 边界检查
        if index < 0 or index >= self.size:
            return
        
        current = self.dummy_head       # 从虚拟头节点开始
        for i in range(index):          # 移动到删除位置的前一个节点
            current = current.next
        # 删除节点(Python自动垃圾回收)
        current.next = current.next.next
        self.size -= 1                  # 链表大小减1

双链表实现(Python)

class ListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val          # 节点值
        self.prev = prev        # 指向上一个节点的引用
        self.next = next        # 指向下一个节点的引用

class MyLinkedList:
    def __init__(self):
        self.head = None        # 头节点
        self.tail = None        # 尾节点
        self.size = 0           # 链表大小

    def get(self, index: int) -> int:
        # 边界检查
        if index < 0 or index >= self.size:
            return -1
        
        # 根据索引位置选择遍历方向
        if index < self.size // 2:
            current = self.head
            for i in range(index):
                current = current.next
        else:
            current = self.tail
            for i in range(self.size - index - 1):
                current = current.prev
                
        return current.val

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val, None, self.head)  # 创建新节点
        if self.head:
            self.head.prev = new_node               # 更新原头节点的前驱
        else:
            self.tail = new_node                    # 如果链表为空,新节点也是尾节点
        self.head = new_node                        # 更新头节点
        self.size += 1                              # 链表大小加1

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val, self.tail, None)  # 创建新节点
        if self.tail:
            self.tail.next = new_node               # 更新原尾节点的后继
        else:
            self.head = new_node                    # 如果链表为空,新节点也是头节点
        self.tail = new_node                        # 更新尾节点
        self.size += 1                              # 链表大小加1

    def addAtIndex(self, index: int, val: int) -> None:
        # 边界检查
        if index < 0 or index > self.size:
            return
        
        if index == 0:
            self.addAtHead(val)                     # 在头部插入
        elif index == self.size:
            self.addAtTail(val)                     # 在尾部插入
        else:
            # 找到插入位置的前一个节点
            if index < self.size // 2:
                current = self.head
                for i in range(index - 1):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index):
                    current = current.prev
            
            # 插入新节点
            new_node = ListNode(val, current, current.next)
            current.next.prev = new_node
            current.next = new_node
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        # 边界检查
        if index < 0 or index >= self.size:
            return
        
        if index == 0:
            # 删除头节点
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
        elif index == self.size - 1:
            # 删除尾节点
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            # 删除中间节点
            if index < self.size // 2:
                current = self.head
                for i in range(index):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index - 1):
                    current = current.prev
            
            # 删除节点
            current.prev.next = current.next
            current.next.prev = current.prev
        
        self.size -= 1                              # 链表大小减1

算法技巧总结

1. 虚拟头节点技巧

  • 作用:统一操作逻辑,简化边界条件
  • 适用场景:需要修改头节点的操作
  • 实现要点:记得释放虚拟头节点的内存

2. 双向遍历优化

  • 原理:根据索引位置选择更短的遍历路径
  • 实现:比较索引与链表长度的一半
  • 效果:将平均时间复杂度从O(n)降低到O(n/2)

3. 边界条件处理

  • 索引检查:确保索引在有效范围内
  • 空链表处理:处理链表为空的情况
  • 单节点处理:处理只有一个节点的情况

4. 内存管理

  • C++:手动释放内存,避免内存泄漏
  • Python/Java:自动垃圾回收,无需手动管理

5. 循环双链表设计

  • 哨兵节点:简化边界条件处理
  • 循环连接:统一头尾节点的操作
  • 双向指针:支持双向遍历

总结

核心要点

  1. 虚拟头节点是链表操作的核心技巧,能够大大简化代码逻辑
  2. 双链表通过双向遍历优化,提高查找效率
  3. 边界条件处理是链表操作的关键,需要仔细考虑各种情况
  4. 内存管理在不同语言中有不同的处理方式

学习建议

  1. 掌握虚拟头节点:理解其原理和应用场景
  2. 熟练链表操作:掌握增删改查的基本操作
  3. 理解性能优化:学会选择合适的链表类型
  4. 注意边界条件:养成良好的编程习惯

进阶方向

  1. 链表排序:归并排序、快速排序在链表上的应用
  2. 链表检测:环检测、相交检测等高级操作
  3. 链表反转:部分反转、K个一组反转等
  4. 链表合并:多链表合并、有序链表合并等

设计链表这道题是链表操作的集大成者,掌握好这道题,就能应对大部分链表相关的问题。通过虚拟头节点、双向遍历等技巧,我们能够写出高效、健壮的链表实现。


代码调试


// 可以写在外面吗? 实测可以
struct LinkedNode {
    int val; 
    LinkedNode* next;
    LinkedNode() : val(0), next(nullptr) {}
    LinkedNode(int val) : val(val), next(nullptr) {}
    LinkedNode(int val, LinkedNode* next) : val(val), next(next) {}
};


class MyLinkedList {
public:
    // 在单链表内部定义节点结构体
    // struct LinkedNode {
    //     int val;
    //     LinkedNode* next;
    //     LinkedNode() : val(0), next(nullptr) {}
    //     LinkedNode(int x) : val(x), next(nullptr) {}
    //     LinkedNode(int x, LinkedNode* next) : val(x), next(next) {}
    // }; // 能写出去吗?

    // 构造函数初始化单向链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);  // 虚拟头节点,须分配内存
        _size = 0;                      // 初始化链表大小为0
    }
    
    // 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
    // index索引位置的值
    int get(int index) {
        // 关键点:索引是否越界?
        if (index > (_size - 1) || index < 0) {
            return -1;
        } 
        // LinkedNode* cur = _dummyHead;
        // while (index--) {
        //     cur = cur->next;
        // }
        // return cur->next->val;
        LinkedNode* cur = _dummyHead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    

    // 头部插入 (虚拟头节点 ——> 真头节点)
    // 目前:(_dummyHead->next==TRUEhead)
    // 目标:(newNode ——> TRUEhead)
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val); // 创建新节点
        // 原来的头节点是 _dummyHead->next
        newNode->next = _dummyHead->next;       // 新节点接上原来的头节点
        _dummyHead->next = newNode;             // 更新虚拟头节点
        _size++;                                // 链表长度+1
    }
    

    // 尾部插入 ——> 1.找到尾部位置 2. 插入
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val); // 分配内存, 创建节点
        LinkedNode* cur = _dummyHead;               // cur从虚拟头节点开始遍历
        // 关键问题: 循环不变量和循环条件?cur==最后一个节点时, 执行插入操作!
        while (cur->next != nullptr) {          // 找到最后一个节点
            cur = cur->next;
        }
        // 此时cur就是单链表最后一个元素了
        cur->next = newNode;            // 连接新节点
        _size++;                        // 链表大小
    }
    

    // 增加一个Index下标位置节点
    void addAtIndex(int index, int val) {
        // 涉及到index的操作都需要检查边界!
        if (index > (_size - 1) || index < 0) {
            return;     // 什么也不做直接返回
        }
        LinkedNode* cur = _dummyHead;
        LinkedNode* newNode = new LinkedNode(val);
        while (index--) {
            cur = cur->next;
        }
        // cur 【index位置 要插入newNode】  cur->next
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    

    // 删除Index下标位置的节点
    void deleteAtIndex(int index) {
        if (index > (_size - 1) || index < 0) {
            return;     // 什么也不做直接返回
        }
        LinkedNode* cur = _dummyHead;
        while (index--) {
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;         // 释放被删除节点的内存
        tmp = nullptr;      // 避免野指针
        _size--;
    }

    // 打印链表用于调试
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
    }
private:                            // _xxx 表示封装为内部变量
    LinkedNode* _dummyHead;         // 虚拟头节点定义
    int _size;                      // 链表大小
};

int mian() {
    
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

有个用例一直通过不了,想打印检查看看!
一番调试后发现就是边界检查的问题

涉及到索引的问题都要注意边界检查!


// 可以写在外面吗? 实测可以
struct LinkedNode {
    int val; 
    LinkedNode* next;
    LinkedNode() : val(0), next(nullptr) {}
    LinkedNode(int val) : val(val), next(nullptr) {}
    // LinkedNode(int val, LinkedNode* next) : val(val), next(next) {}
};


class MyLinkedList {
public:
    // 在单链表内部定义节点结构体
    // struct LinkedNode {
    //     int val;
    //     LinkedNode* next;
    //     LinkedNode() : val(0), next(nullptr) {}
    //     LinkedNode(int x) : val(x), next(nullptr) {}
    //     LinkedNode(int x, LinkedNode* next) : val(x), next(next) {}
    // }; // 能写出去吗?

    // 构造函数初始化单向链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);  // 虚拟头节点,须分配内存
        _size = 0;                      // 初始化链表大小为0
    }
    
    // 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
    // index索引位置的值
    int get(int index) {
        // 关键点:索引是否越界?
        if (index > (_size - 1) || index < 0) {
            return -1;
        } 
        // LinkedNode* cur = _dummyHead;
        // while (index--) {
        //     cur = cur->next;
        // }
        // return cur->next->val;
        LinkedNode* cur = _dummyHead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
        // printLinkedList();
    }
    

    // 头部插入 (虚拟头节点 ——> 真头节点)
    // 目前:(_dummyHead->next==TRUEhead)
    // 目标:(newNode ——> TRUEhead)
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val); // 创建新节点
        // 原来的头节点是 _dummyHead->next
        newNode->next = _dummyHead->next;       // 新节点接上原来的头节点
        _dummyHead->next = newNode;             // 更新虚拟头节点
        _size++;                                // 链表长度+1
        // printLinkedList();
    }
    

    // 尾部插入 ——> 1.找到尾部位置 2. 插入
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val); // 分配内存, 创建节点
        LinkedNode* cur = _dummyHead;               // cur从虚拟头节点开始遍历
        // 关键问题: 循环不变量和循环条件?cur==最后一个节点时, 执行插入操作!
        while (cur->next != nullptr) {          // 找到最后一个节点
            cur = cur->next;
        }
        // 此时cur就是单链表最后一个元素了
        cur->next = newNode;            // 连接新节点
        _size++;                        // 链表大小
        // printLinkedList();
    }
    

    // 增加一个Index下标位置节点
    void addAtIndex(int index, int val) {
        // 涉及到index的操作都需要检查边界!
/********************检查出来了!这里逻辑有问题!***********************/
        // if (index >= _size || index < 0) {

        //     printLinkedList();            
        //     return;     // 什么也不做直接返回
        // }
/********************检查出来了!这里逻辑有问题!***********************/
        
        if (index < 0) addAtHead(val);

        if  (index > _size) return;

        LinkedNode* cur = _dummyHead;
        LinkedNode* newNode = new LinkedNode(val);
        while (index--) {
            cur = cur->next;
        }
        // cur 【index位置 要插入newNode】  cur->next
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
        // printLinkedList();
        
    }
    

    // 删除Index下标位置的节点
    void deleteAtIndex(int index) {
        if (index > (_size - 1) || index < 0) {
            // printLinkedList();

            return;     // 什么也不做直接返回
        }
        LinkedNode* cur = _dummyHead;
        while (index--) {
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;         // 释放被删除节点的内存
        tmp = nullptr;      // 避免野指针
        _size--;

        // printLinkedList();
    }

    // 打印链表用于调试
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " " ;
            cur = cur->next;
        }
        cout << endl;
    }
private:                            // _xxx 表示封装为内部变量
    LinkedNode* _dummyHead;         // 虚拟头节点定义
    int _size;                      // 链表大小
};


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

更多推荐