LeetCode 707 设计链表

这题看起来是在考链表，实际上主要是在考你对指针顺序和边界条件的掌控力。只要把虚拟头节点用好，很多麻烦会直接少一半。

题目信息

  • 平台：LeetCode
  • 题目：707. 设计链表
  • 难度：中等
  • 题目链接：设计链表

题意

设计一个链表，支持以下操作：

  1. get(index)：获取下标对应节点的值。
  2. addAtHead(val)：在头部插入节点。
  3. addAtTail(val)：在尾部插入节点。
  4. addAtIndex(index, val)：在指定位置插入节点。
  5. deleteAtIndex(index)：删除指定位置的节点。

这道题的关键在于：所有操作都可以统一成“找到前驱节点，再做指针修改”。

思路

1. 使用虚拟头节点

这里采用了一个 dummyHead 作为虚拟头节点。

这样做的好处很明显：

  • 插入头节点时，不需要单独处理空链表。
  • 删除头节点时，也不需要额外特判。
  • 所有“在某个位置前面插入 / 删除”的操作，都可以统一成找前驱节点。

2. 维护链表长度 size

为了方便判断下标是否合法，直接维护一个 size。

  • get(index)：要求 0 <= index < size
  • addAtIndex(index, val)：要求 0 <= index <= size
  • deleteAtIndex(index)：要求 0 <= index < size

这样一来，边界判断会非常清晰。

3. 插入时先改新节点的 next

这是这题最容易写错的地方。

插入节点时，正确顺序应该是：

  1. nodeTemp->next = cur->next
  2. cur->next = nodeTemp

如果顺序反了，原来的链就容易断掉，节点也可能直接丢失。

4. 删除时先保存待删节点

删除节点时，先保存 cur->next，再跳过它，最后 delete 释放。

这样写更稳，也更不容易出错。

代码

class MyLinkedList {
public:
  class Node {
  public:
    int val;
    Node *next;
    Node(int _val) : val(_val), next(NULL) {}
  };

  MyLinkedList() {
    _dummyHead = new Node(0);
    _size = 0;
  }

  int get(int index) {
    if (index < 0 || index >= _size) {
      return -1;
    }

    Node *cur = _dummyHead;
    while (index--) {
      cur = cur->next;
    }

    return cur->next->val;
  }

  void addAtHead(int val) {
    Node *nodeTemp = new Node(val);
    nodeTemp->next = _dummyHead->next;
    _dummyHead->next = nodeTemp;
    ++_size;
  }

  void addAtTail(int val) {
    Node *nodeTemp = new Node(val);
    Node *cur = _dummyHead;

    while (cur->next != NULL) {
      cur = cur->next;
    }

    cur->next = nodeTemp;
    ++_size;
  }

  void addAtIndex(int index, int val) {
    if (index < 0 || index > _size) {
      return;
    }

    Node *cur = _dummyHead;
    Node *nodeTemp = new Node(val);

    while (index--) {
      cur = cur->next;
    }

    nodeTemp->next = cur->next;
    cur->next = nodeTemp;
    ++_size;
  }

  void deleteAtIndex(int index) {
    if (index < 0 || index >= _size) {
      return;
    }

    Node *cur = _dummyHead;
    while (index--) {
      cur = cur->next;
    }

    Node *nodeTemp = cur->next;
    cur->next = cur->next->next;
    delete nodeTemp;
    --_size;
  }

private:
  Node *_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);
 */

复杂度分析

  • get：
  • addAtHead：
  • addAtTail：
  • addAtIndex：
  • deleteAtIndex：

由于链表的本质就是“靠遍历找位置”，所以除了头插以外，大部分操作都绕不开线性时间。

容易踩的坑

  • 忘记判断 index 的合法性。
  • addAtIndex 里把 index == size 误判成非法。
  • 插入节点时先改前驱指针，导致链表断开。
  • 删除节点时没有先保存待删节点，后续无法释放内存。

总结

这题的核心其实只有一句话：所有操作都统一成“找前驱，再改指针”。

虚拟头节点把头插、头删这些边界情况全部抹平了，写起来会顺手很多。以后遇到类似的链表题，先想清楚“我要找的是当前节点，还是前驱节点”，通常就不会乱。