leetcode 707 设计链表

女爷i 2022-09-08 13:51 151阅读 0赞

## 前言 ##

题目：[707. 设计链表][707.]

参考答案：[707.设计链表 - 代码随想录][707._ -]

本文档详细代码见：[git仓库][git]

--------------------

## 提交代码 ##

既然是自己设计链表，自然选择自己喜欢的结构。

*  相对于单链表，我更喜欢双链表。双链表虽然占用的空间多些，但操作更加方便。双链表首尾相连，形成环装。
 *  我喜欢增加一个不存储数据的表头，这样操作方便。相关描述可参见[leetcode 203 移除链表元素][leetcode 203]
 *  为了减少一个复杂度，我没有使用一个属性来记录链表的长度。

好了，来设计我们的链表吧。

#include <iostream>
    #include <vector>
    #include <ctime>
    
    using namespace std;
    
    class MyLinkedList {
    public:
        /** 定义节点*/
        struct LinkNode{
            int val;
            LinkNode* next;
            LinkNode* prev;
            LinkNode() : val(0), next(nullptr),prev(nullptr) {}
            LinkNode(int x) : val(x), next(nullptr),prev(nullptr) {}
        };
    
        /** Initialize your data structure here. */
        MyLinkedList() {
            head = new LinkNode();
            head->next = head;
            head->prev = head;
        }
        
        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        int get(int index) {
            LinkNode* it = head->next;
            int i=0;
            for(; it!=head && i<index; it=it->next,i++){
                ;
            }
            if(it != head && i==index)
                return it->val;
            else
                return -1;
        }
        
        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        void addAtHead(int val) {
            LinkNode* addNode = new LinkNode(val);
            LinkNode* headNext = head->next;
            
            head->next = addNode;
            addNode->prev = head;
            addNode->next = headNext;
            headNext->prev = addNode;
        }
        
        /** Append a node of value val to the last element of the linked list. */
        void addAtTail(int val) {
            // 我让数据结构为双链表的好处来了。插入尾部的时候，等效与插在head之前
            LinkNode* addNode = new LinkNode(val);
            LinkNode* headPrev = head->prev;
            
            head->prev = addNode;
            addNode->next = head;
            addNode->prev = headPrev;
            headPrev->next = addNode;
        }
        
        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        void addAtIndex(int index, int val) {
            LinkNode* it = head->next;
            int i=0;
            while(it!=head && i<index){
                it = it->next;
                i++;
            }
            if(it!=head && i==index){// 插入在链表内
                LinkNode* addNode = new LinkNode(val);
                LinkNode* itPrev = it->prev;
    
                itPrev->next = addNode;
                addNode->next = it;
                it->prev = addNode;
                addNode->prev = itPrev;
                return;
            }
            if(it==head && i==index){ // 插在尾部
                this->addAtTail(val);
                return;
            }
            // 超出范围了，咱不干了
        }
        
        /** Delete the index-th node in the linked list, if the index is valid. */
        void deleteAtIndex(int index) {
            LinkNode* it = head->next;
            int i=0;
            while(it!=head && i<index){
                it = it->next;
                i++;
            }
            if(it!=head && i==index){ // 在链表范围内
                LinkNode* itPre = it->prev;
                LinkNode* itNext = it->next;
    
                itPre->next = itNext;
                itNext->prev = itPre;
                delete it;
            }
            // 超出范围
        }
    
    private:
        LinkNode* head; // 头节点不存储元素
        // 不添加size属性了，也不用head的val来存储，避免引入复杂度
    };
    
    /**
     * 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);
     */
    
    int main(void){
    
        MyLinkedList* linkedList = new MyLinkedList();
        linkedList->addAtHead(1);
        linkedList->addAtTail(3);
        linkedList->addAtIndex(1,2);//链表变为1-> 2-> 3
        for(int i=0; i<3; i++)
            cout<<linkedList->get(i)<<" ";            
        linkedList->deleteAtIndex(1);  //现在链表是1-> 3
        cout<<linkedList->get(1)<<" ";            //返回3
    }

[707.]: https://leetcode-cn.com/problems/design-linked-list/
[707._ -]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.md
[git]: https://github.com/da1234cao/data_structure/tree/master/leetcode
[leetcode 203]: https://blog.csdn.net/sinat_38816924/article/details/119928145