LeetCode 707.设计链表

张威大约 3 分钟

题目描述：在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

index是从0开始的

可创建虚拟头节点简化操作

单链表

//单向链表
class MyLinkedList {
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int val = 0, ListNode* next = nullptr) : val(val), next(next) {}
    };
    MyLinkedList() {
        _dummyHead = new ListNode(0, nullptr);
        _size = 0;
    }
    
    int get(int index) {
        if(index < 0||index >= _size) {
            return -1;
        }
        ListNode* pcur = _dummyHead->next;  //第一个数据结点
        while(index--) {
            pcur = pcur->next;
        }
        return pcur->val;
    }
    
    void addAtHead(int val) {
        ListNode* ptemp = new ListNode(val, _dummyHead->next);
        _dummyHead->next = ptemp;
        ++_size;
    }
    
    void addAtTail(int val) {
        ListNode* pcur = _dummyHead;//需要前驱结点，真正要插入位置pcur->next
        while(pcur->next) {
            pcur = pcur->next;
        }
        ListNode*ptemp = new ListNode(val, nullptr);
        pcur->next = ptemp;
        ++_size;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0 || index > _size) {
            return;
        }
        ListNode* pcur = _dummyHead;
        while(index--) {
            pcur = pcur->next;
        }
        ListNode* ptemp = new ListNode(val, pcur->next);
        pcur->next = ptemp;
        ++_size;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= _size) {
            return;
        }
        ListNode* pcur = _dummyHead;
        while(index--) {
            pcur = pcur->next;
        }
        ListNode* ptemp = pcur->next;
        pcur->next = pcur->next->next;
        delete ptemp;
        ptemp = nullptr;
        --_size;
    }
private:
    ListNode* _dummyHead;
    size_t _size;
};

/**
 * 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);
 */

实现 addAtHead(val)和 addAtTail(val)时，可以借助 addAtIndex(index, val)来实现。

void addAtHead(int val) {
	addAtIndex(0, val);
}
    
void addAtTail(int val) {
    addAtIndex(_size, val);
}

双向链表

//双向链表
struct DLinkedListNode {
    int val;
    DLinkedListNode *pre, *next;   //注意同时定义两个指针的方法
    DLinkedListNode(int val = 0, DLinkedListNode* pre = nullptr,DLinkedListNode* next = nullptr) : val(val), pre(pre), next(next) {}
};

class MyLinkedList {
private:
    DLinkedListNode* findElement(int index,DLinkedListNode* pcur = nullptr) {
 //先定义游标，在判断是靠近_phead还是_ptail
        if(index <= _size/2) { //前-半
            pcur = _phead;//指向第一个结点
            for(int i = 0; i < index + 1; ++i) {   
                pcur = pcur->next;
            }
        }
        else {//后一半
            pcur = _ptail;
            for(int i = 0; i < _size - index; ++i) {  //_size - index正好pcur = 目标
                pcur = pcur->pre;
            }
        }
        return pcur;
    }

public:
    MyLinkedList() {
        _size = 0;
        _phead = new DLinkedListNode();
        _ptail = new DLinkedListNode();
        _phead->next = _ptail;
        _ptail->pre = _phead;
    }
    

    int get(int index) {
        if(index < 0 || index >= _size) {
            return -1;
        }
        DLinkedListNode* res = findElement(index);
        return res->val;
    }
    
    void addAtHead(int val) {
        //addAtIndex(0, val);
        DLinkedListNode* newNode = new DLinkedListNode(val,_phead,_phead->next);
        _phead->next->pre = newNode;
        _phead->next = newNode;
        ++_size;
    }
    
    void addAtTail(int val) {
        //addAtTail(_size, val);
        DLinkedListNode* newNode = new DLinkedListNode(val, _ptail->pre, _ptail);
        _ptail->pre->next = newNode;
        _ptail->pre = newNode;
        ++_size;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0||index > _size) {
            return;
        }

        DLinkedListNode* pcur = findElement(index);
        DLinkedListNode* newNode = new DLinkedListNode(val, pcur->pre, pcur);
        pcur->pre->next = newNode;
        pcur->pre = newNode;
        
        ++_size;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0||index >= _size) {
            return;
        }
        DLinkedListNode* pcur = findElement(index);
        pcur->next->pre = pcur->pre;
        pcur->pre->next = pcur->next;
        delete pcur;
        pcur = nullptr;
        --_size;
    }

private:
    int _size;
    DLinkedListNode* _phead;
    DLinkedListNode* _ptail;
};

/**
 * 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);
 */

单链表：关键找到前驱，真正插入或者删除的元素是pcur->next
双向链表：关键是找到目标元素，借助pre和next指针完成插入和删除

LeetCode 707.设计链表

# 单链表

# 双向链表

单链表

双向链表