手把手教你完整实现一个链表
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
上一篇文章当中我们介绍了链表的原理以及一些基本操作，今天我们来实际练习一下，进一步加深一下印象。
我们先来看一道基础题，LeetCode 203，移除链表元素。
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
分析
本题是链表应用的裸题，考察的是对链表删除操作的掌握。我们很容易就写出代码：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* pt = head;
// 使用while循环遍历链表
while (pt != nullptr && pt->next != nullptr) {
if (pt->next->val == val) {
pt->next = pt->next->next;
// 注意这里的else
}else pt = pt->next;
}
return head;
}
};
注意一点小细节，由于链表的删除操作是pt->next = pt->next->next。即将当前的next指针指向再之后的一个元素，这就导致了我们每次判断的都是下一个元素是否要删除，而非当前元素。并且，在删除了下一个元素之后，虽然当前指针没有变化，但下一个元素已经变了，所以我们不需要移动指针了。
另外还有一个小问题：如果开头就是要删除的元素怎么办，我们没有比head更早的节点了，又怎么删除head呢？如果试着提交一下上面的代码， 就会发现无法通过头一个元素就需要删除的case。
针对这个问题，一种比较容易想到的方法是我们先对链表的头部进行特判，先将头部所有等于val的节点全部删除，找到新的head指针之后，再执行上面的操作。
这当然是没问题的，但解决这个问题，我们有更优雅的方法，并且这个方法的使用频率非常高，几乎在所有链表相关的问题中都可以使用。
这个方法就是创建一个虚拟的头节点，这个头节点是我们创建出来的，所以无论如何它都不会删除。所以不知道返回的头节点是什么的问题也就不存在了。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* nd = new ListNode();
nd->next = head;
ListNode* pt = nd;
while (pt != nullptr && pt->next != nullptr) {
if (pt->next->val == val) {
auto tmp = pt->next;
pt->next = pt->next->next;
delete tmp;
}else pt = pt->next;
}
return nd->next;
}
};
小试牛刀之后我们再来看一题：LeetCode 707 设计链表。
设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第
index个节点的值。如果索引无效，则返回-1。 - addAtHead(val)：在链表的第一个元素之前添加一个值为
val的节点。插入后，新节点将成为链表的第一个节点。 - addAtTail(val)：将值为
val的节点追加到链表的最后一个元素。 - addAtIndex(index,val)：在链表中的第
index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 - deleteAtIndex(index)：如果索引
index有效，则删除链表中的第index个节点。
分析
在这道题当中我们要实现一个链表的类，提供题意当中列举的这些方法。
LeetCode当中这类的问题很多，平台已经为我们定义好了代码框架，我们只需要实现细节。这是一个了解和学习面向对象非常好的机会，强烈建议初学乍练的萌新不要错过。
class MyLinkedList {
public:
MyLinkedList() {
}
int get(int index) {
}
void addAtHead(int val) {
}
void addAtTail(int val) {
}
void addAtIndex(int index, int val) {
}
void deleteAtIndex(int index) {
}
};
/**
* 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);
*/
首先声明，这道题因为涉及末尾插入元素以及指定下标添加、删除元素，涉及的细节更多，要比看起来的更困难一些。
观察代码可以发现只是替我们定义好了链表的类，没有链表中节点的相关定义，首先写好这个部分：
class MyLinkedList {
public:
struct Node {
int val;
Node* next;
Node(int x, Node* pt=nullptr): val(x), next(pt) {}
};
...
题目中需要我们往末尾插入元素的操作，因此我们除了需要head之外，还需要一个tail记录最后一个元素。head是虚拟头节点，永远不变，而tail是尾节点，指向最后一个节点的位置。因此随着我们的操作，tail可能会发生变化。这一点非常重要，切记。
初始化时我们令tail = head，这样才能保证不论我们往头部还是尾部插入元素得到的结果相同。
Node *head, *tail;
MyLinkedList() {
head = new Node(0);
tail = head;
}
我非常推荐在开始编码之前先实现一个printAll函数，用来打印链表当中的所有元素。这样会比较方便我们debug。
void printAll() {
auto pt = head;
while (pt->next != nullptr) {
cout << pt->next->val << endl;
pt = pt->next;
}
}
之后从易到难，我们先来实现最简单的从头部插入元素以及从末尾插入元素。
void addAtHead(int val) {
head->next = new Node(val, head->next);
// 注意移动tail
if (head == tail) tail = head->next;
}
void addAtTail(int val) {
tail->next = new Node(val, nullptr);
// 移动tail
tail = tail->next;
}
addAtTail很简单，我们在tail指针后面创建一个新的节点即可，但别忘了创建好了之后当前的tail就不是最后一个节点的位置了，要更新一下。
同样在addAtHead函数当中也有这个问题，刚开始的时候链表为空，往head后面添加元素就相当于往末尾添加。因此要加上特判，当head等于tail时，也要更新tail。
接下来比较好实现的是get函数，需要返回指定下标的元素。我们只需要使用for循环从head开始移动index+1次，如果没到链表结尾的话，返回指向的元素即可。
int get(int index) {
auto pt = head;
for (int i = 0; i <= index; i++) {
pt = pt->next;
if (pt == nullptr) return -1;
}
return pt->val;
}
get没问题了之后，稍微修改一下就是addAtIndex函数。这里要小心，由于我们在插入元素的时候都会修改插入之前的节点，所以这里我们只需要移动index次，比上面要少一次。
void addAtIndex(int index, int val) {
auto pt = head;
for (int i = 0; i < index; i++) {
pt = pt->next;
if (pt == nullptr) return ;
}
pt->next = new Node(val, pt->next);
if (pt == tail) tail = pt->next;
}
最后才是删除元素，基本上是插入元素的逆操作。除了小心空指针之外，还要注意如果删除的节点刚好是tail，要把tail往前移。
void deleteAtIndex(int index) {
auto pt = head;
for (int i = 0; i < index; i++) {
pt = pt->next;
if (pt == nullptr) return ;
}
auto tmp = pt->next;
if (tmp == nullptr) return ;
pt->next = pt->next->next;
if (tmp == tail) tail = pt;
delete tmp;
}
最后贴一下完整代码：
class MyLinkedList {
public:
struct Node {
int val;
Node* next;
Node(int x, Node* pt=nullptr): val(x), next(pt) {}
};
Node *head, *tail;
MyLinkedList() {
head = new Node(0);
tail = head;
}
int get(int index) {
auto pt = head;
for (int i = 0; i <= index; i++) {
pt = pt->next;
if (pt == nullptr) return -1;
}
return pt->val;
}
void addAtHead(int val) {
head->next = new Node(val, head->next);
if (head == tail) tail = head->next;
}
void addAtTail(int val) {
tail->next = new Node(val, nullptr);
tail = tail->next;
}
void addAtIndex(int index, int val) {
auto pt = head;
for (int i = 0; i < index; i++) {
pt = pt->next;
if (pt == nullptr) return ;
}
pt->next = new Node(val, pt->next);
if (pt == tail) tail = pt->next;
}
void deleteAtIndex(int index) {
auto pt = head;
for (int i = 0; i < index; i++) {
pt = pt->next;
if (pt == nullptr) return ;
}
auto tmp = pt->next;
if (tmp == nullptr) return ;
pt->next = pt->next->next;
if (tmp == tail) tail = pt;
delete tmp;
}
};