K - 双向链表练习题

A：好的，下面是K - 双向链表练习题的解答。

题目描述：

设计一个数据结构，要求实现双向链表的基本操作：插入、删除、反转等，并实现一个方法向链表中添加一个元素。同时，该数据结构需要支持以下操作：

1. get(k)：返回链表中第 k 个节点的值。如果 k 小于 1 或大于链表的长度，则返回 -1。

2. addAtHead(val)：在链表的头部插入一个值为 val 的节点。

3. addAtTail(val)：在链表的尾部插入一个值为 val 的节点。

4. addAtIndex(index,val)：在链表中的第 index 个节点前插入一个值为 val 的节点。如果 index 等于链表的长度，则在链表的末尾添加该节点。如果 index 大于链表的长度，则不会插入。

5. deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

解题思路：

题目要求我们设计一个双向链表数据结构，并提供选定的一些操作。这是一个经典的链表问题，我们需要先设计链表节点的结构体，并在节点中保留前驱和后继指针，便于双向操作。然后，我们可以定义一个链表类，在该类中定义一些方法来实现链表的基本操作。

本题需要实现的方法包括：

1. get(k)：遍历链表，找到第 k 个节点并返回该节点的值。

2. addAtHead(val)：创建一个新节点，将该节点作为头节点，并更新头节点的前驱指针。

3. addAtTail(val)：创建一个新节点，将该节点作为尾节点，并更新尾节点的后继指针。

4. addAtIndex(index,val)：遍历链表，找到第 index - 1 个节点，创建一个新节点，并将其插入到该节点的后面。如果 index 为零，则将新节点插入到头部。如果 index 等于链表的长度，则将新节点插入到末尾。

5. deleteAtIndex(index)：遍历链表，找到第 index - 1 个节点，并将其后继指针指向第 index + 1 个节点。如果 index 为零，则更新头节点。如果 index 等于链表的长度 - 1，则更新尾节点。

代码实现：

下面是基于C++的实现代码，其中Node是一个链表节点的结构体，List是链表类的定义：

#include<iostream>
using namespace std;

// 链表节点结构体
struct Node {
    int val;        // 节点的值
    Node* pre;      // 前驱指针
    Node* nxt;      // 后继指针
    Node(int _val):val(_val),pre(nullptr),nxt(nullptr){}  // 构造函数
};

// 链表类
class List{
private:
    Node* head;     // 头节点
    Node* tail;     // 尾节点
    int size;       // 链表长度

public:
    List():head(nullptr),tail(nullptr),size(0){}         // 构造函数

    int get(int k){                             
        if(k < 1 || k > size)                       // 判断k是否合法
            return -1;
        Node* p = head;
        for(int i=1; i<k; i++)                      // 遍历链表，找到第k个节点
            p = p->nxt;
        return p->val;                             // 返回节点的值
    }

    void addAtHead(int val){
        Node* p = new Node(val);                    // 创建新节点
        if(size == 0){                              // 链表为空的情况
            head = p;                               
            tail = p;
        }else{                                      // 链表非空的情况
            p->nxt = head;                          // 插入节点
            head->pre = p;
            head = p;
        }
        size++;                                     // 更新链表长度
    }

    void addAtTail(int val){
        Node* p = new Node(val);                    // 创建新节点
        if(size == 0){                              // 链表为空的情况
            head = p;
            tail = p;
        }else{                                      // 链表非空的情况
            tail->nxt = p;                          // 插入节点
            p->pre = tail;
            tail = p;
        }
        size++;                                     // 更新链表长度
    }

    void addAtIndex(int index, int val){
        if(index > size)                            // index不合法，不插入
            return;
        if(index <= 0)                              // 如果index小于等于0，插入到头部
            addAtHead(val);
        else if(index == size)                      // 如果index等于size，插入到尾部
            addAtTail(val);
        else{                                       // 如果index在链表中
            Node* p = head;
            for(int i=1; i<index; i++)              // 找到第index-1个节点
                p = p->nxt;
            Node* q = new Node(val);                // 创建新节点
            q->nxt = p->nxt;                        // 插入节点
            p->nxt->pre = q;
            p->nxt = q;
            q->pre = p;
            size++;                                 // 更新链表长度
        }
    }

    void deleteAtIndex(int index){
        if(index < 0 || index >= size)              // index不合法，不删除
            return;
        if(index == 0){                             // 如果要删除的是头节点
            head = head->nxt;                       // 更新头节点
            if(head == nullptr)                     // 如果链表为空，尾节点也需要更新
                tail = nullptr;
            else
                head->pre = nullptr;
        }else if(index == size-1){                  // 如果要删除的是尾节点
            tail = tail->pre;                       // 更新尾节点
            tail->nxt = nullptr;
        }else{                                      // 如果要删除的是中间节点
            Node* p = head;
            for(int i=1; i<index; i++)              // 找到第index-1个节点
                p = p->nxt;
            p->nxt = p->nxt->nxt;                   // 删除节点
            p->nxt->pre = p;
        }
        size--;                                     // 更新链表长度
    }
};

int main(){
    List l;
    l.addAtHead(1);
    l.addAtTail(3);
    l.addAtIndex(1,2);                  // 链表变为[1,2,3]
    cout<<l.get(1)<<" ";                // 返回2
    l.deleteAtIndex(1);                 // 现在链表是[1,3]
    cout<<l.get(1)<<" ";                // 返回3
    return 0;
}

总结：

双向链表实现相对较多的语言，相对单向链表更适合一些场景；比如说LUR Cache。对于双向链表的实现，我们需要注意节点间指针的指向关系，以及头节点和尾节点的处理。感兴趣的读者可以继续尝试其他链表问题，如链表的分割、链表的反转等。