腾讯云

文章/答案/技术大牛

发布

社区首页 >专栏 >手把手教你完整实现一个链表

手把手教你完整实现一个链表

TechFlow-承志

发布于 2023-03-02 07:01:02

25300

代码可运行

文章被收录于专栏：TechFlowTechFlow

运行总次数：0

代码可运行

作者 | 梁唐

出品 | 公众号：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;
    }
};