您现在的位置是：首页 >学无止境 >算法-链表篇02-设计链表网站首页学无止境

设计链表

力扣题目链接

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

解题思路

这道题的题目给人误解挺大的，个人认为应该是对链表进行更高一级的抽象或者封装，而不是设计链表，希望大家也能给出不同的见解。
我首先实现了一个链表，然后告诉我应该使用自带的ListNode。
所以，这道题就是使用ListNode实现一层方便集中链表操作的封装类。首先对题目的需求进行分析，这个类中只需要包含两个元素链表的头结点m_head和长度m_index。
接下来逐一分析各个方法的实现：

• MyLinkedList() 需要创建头结点和链表大小赋值为-1；
• int get(int index) 方法则是判断下标是否存在，然后循环遍历index次，获取到该节点的值；
• void addAtHead(int val) 方法是在第零个节点处插入一个值为val的节点，所以我门需要先创建一个节点赋值val，然后将该节点插入到第零个位置；
• void addAtTail(int val) 方法是在最后一个节点后方插入一个值为val的节点，所以我们需要创建开节点赋值为val，然后循环遍历链表，直到后继节点为空，这时把最后一个节点的后继节点指向该节点；
• void addAtIndex(int index, int val) 方法需要先判断这个index是否存在，然后循环遍历index次，创建一个val节点插入在该位置上；
• void deleteAtIndex(int index) 方法先判断index是否存在，然后循环遍历到index的位置，然后删除改节点；

题解

//单链表版本
class MyLinkedList {
private:
    int m_index;
    ListNode* m_head;
public:
    MyLinkedList() {
        m_index = -1;
        m_head = new ListNode(0);
    }

    int get(int index) {
        if(m_index == -1){
            //throw "List is empty";
            return -1;
        }
        else if(index > m_index){
            //throw "index is out of range";
            return -1;
        }
        else {
            ListNode* p = m_head;
            for(int i = 0; i <= index; i++){
                p = p->next;
                cout << p->val << endl;
            }
            return p->val;
        }
    }

    void addAtHead(int val) {
        ListNode* temp = new ListNode(val);
        temp->next = m_head->next;
        m_head->next = temp;
        m_index++;
    }

    void addAtTail(int val) {
        ListNode* temp = new ListNode(val);
        ListNode* head = m_head;
        while (head->next != nullptr) {
            head = head->next;
        }
        head->next = temp;
        m_index++;
    }

    void addAtIndex(int index, int val) {
        if (index > m_index + 1) {
            //throw "index is out of range";
            return;
        }
        else {
            ListNode* temp = new ListNode(val);
            ListNode* p = m_head;
            for (int i = 0; i < index; i++) {
                p = p->next;
            }
            temp->next = p->next;
            p->next = temp;
            m_index++;
        }
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index > m_index) {
            //throw "index is out of range";
            return;
        }
        else {
            ListNode* p = m_head;
            for (int i = 0; i < index; i++) {
                p = p->next;
            }
            ListNode* temp = p->next;
            p->next = temp->next;
            delete temp;
            m_index--;
        }
    }
};

总结

这道题的整体难度不大，但是很多人在实现的时候会面临各种问题，我在完成这道题目的时候，就遇到了很多错误，主要是没有确定边界问题。例如：循环应该u进行多少次？对于要处理index应该是遍历到前一个位置还是该位置？判断index越界是大于还是大于等于？这些问题时需要在写代码实现功能时就需要确定的，否则在力扣上没法debug，本地没有输入输出环境，排查问题会很麻烦。