Task

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

  • get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
  • addAtHead(val) : 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.
  • addAtTail(val) : Append a node of value val to the last element of the linked list.
  • addAtIndex(index, val) : 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.
  • deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input: 
["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
[[],[1],[3],[1,2],[1],[1],[1]]
Output:  
[null,null,null,null,2,null,3]

Explanation:
MyLinkedList linkedList = new MyLinkedList(); // Initialize empty LinkedList
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2);  // linked list becomes 1->2->3
linkedList.get(1);            // returns 2
linkedList.deleteAtIndex(1);  // now the linked list is 1->3
linkedList.get(1);            // returns 3

Constraints:

  • 0 <= index,val <= 1000
  • Please do not use the built-in LinkedList library.
  • At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Solution

  • 需要含有val和next的节点
  • 链表需要首尾指针便于addAtHead、addAtTail
  • 节点都放在堆内存，链表首尾指针和大小放在栈内存
  • 注意不可内存泄漏
  • 实现：
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

// Runtime: 68 ms, faster than 73.94% of C++ online submissions for Design Linked List.
// Memory Usage: 20 MB, less than 11.11% of C++ online submissions for Design Linked List.
//实现含val和next的节点
class LinkNode{
public:
    int val;
    LinkNode *next;
    //三种初始化
    LinkNode(): val(0),next(nullptr) {}
    LinkNode(int val): val(val),next(nullptr) {}
    LinkNode(int val,LinkNode *next): val(val),next(next) {}
    //一个节点析构时将其后所有节点全都delete
    ~LinkNode(){if(next) delete next;}
};
class MyLinkedList {
public:
    int len_;
    LinkNode *head_;
    LinkNode *tail_;
    /** Initialize your data structure here. */
    MyLinkedList(): len_(0),head_(nullptr),tail_(nullptr) {}
    //析构时只需删除头节点，头节点的析构函数会自动删除其后所有节点
    ~MyLinkedList(){
        delete head_;
        len_=0;
        head_=tail_=nullptr;
    }
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if(index<0 || index>=len_) return -1;
        //从头节点一直走到index节点
        LinkNode *curr=head_;
        while(index--)
            curr=curr->next;
        return curr->val;
    }
    /** 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 *curr=new LinkNode(val,head_);
        head_=curr;
        //若原链表为空，则头尾指针都需指向新节点
        if(len_++==0) tail_=curr;
    }
    void deleteAtHead(){
        //若删除后链表为空，则头尾指针都需是nullptr
        if(--len_==0){
            delete head_;
            head_=tail_=nullptr;
        }
        else{
            LinkNode *curr=head_;
            head_=head_->next;
            //由于析构节点时其后节点自动被删除，故需使next为nullptr才可安全删除
            curr->next=nullptr;
            delete curr;
        }
    }
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        LinkNode *curr=new LinkNode(val);
        //若原链表为空，则头尾指针都需指向新节点
        if(len_++==0)
            head_=tail_=curr;
        else{
            tail_->next=curr;
            tail_=curr;
        }
    }
    void deleteAtTail(){
        //若删除后链表为空，则头尾指针都需是nullptr
        if(--len_==0){
            delete tail_;
            head_=tail_=nullptr;
        }
        else{
            //prev指向要删除的尾指针的上一个节点
            LinkNode *prev=head_;
            LinkNode *curr=tail_;
            for(int i=1;i!=len_;++i)
                prev=prev->next;
            tail_=prev;
            tail_->next=nullptr;
            delete curr;
        }
    }
    /** 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) {
        if(index<0 || index>len_) return;
        //在边界上添加时委托addAtHead和addAtTail实现
        if(index==0) return addAtHead(val);
        if(index==len_) return addAtTail(val);
        //prev是要添加的节点的上一个节点
        LinkNode *prev=head_;
        LinkNode *curr=new LinkNode(val);
        for(int i=1;i!=index;++i)
            prev=prev->next;
        curr->next=prev->next;
        prev->next=curr;
        ++len_;
    }
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if(index<0 || index>=len_) return;
        //在边界上删除时委托deleteAtHead和deleteAtTail实现
        if(index==0) return deleteAtHead();
        if(index==len_-1) return deleteAtTail();
        //prev是要删除的节点的上一个节点
        LinkNode *prev=head_;
        LinkNode *curr=head_->next;
        for(int i=1;i!=index;++i){
            prev=prev->next;
            curr=curr->next;
        }
        prev->next=curr->next;
        //只有把next置为空指针才能安全删除
        curr->next=nullptr;
        delete curr;
        --len_;
    }
};
/**
 * 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);
 */