链表

• 先不去钻研规范库里的 List 了，新的 gnu 里写的巨简单恶心人了。
• 链表可分为单链表，双链表，循环链表

// 链表节点
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *prev;  // 指向上一个节点的指针
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}  // 节点的构造函数};

203- 移除链表元素 – 虚构头结点

「设置一个虚构头结点」，这样原链表的所有节点就都能够依照对立的形式进行移除了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 输出：head = [1,2,6,3,4,5,6], val = 6
// 输入：[1,2,3,4,5]

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0, head);
        ListNode* cur = dummyHead;
        while(cur->next != nullptr){if(cur->next->val == val){
                tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{cur = cur->next;}
        }
        return dummyHead->next;
    }
};

707- 设计链表 - 链表增删查改

「链表操作的两种形式：」

• 间接应用原来的链表来进行操作。(x)
• 设置一个虚构头结点在进行操作。(o)

class MyLinkedList {
public:
    /** Define LinkNode **/
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int val_) : val(val_) {};
        ListNode(int val_, ListNode *next_) : val(val_), next(next_){};};
    
    /** Initialize your data structure here. */
    MyLinkedList() {
        listSize = 0;  
        dummyHead = new ListNode(0, nullptr);
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        ListNode *cur = dummyHead -> next;
        if(index > listSize - 1 || index < 0) return -1;
        while(index--){cur = cur->next;}
        return cur->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) {ListNode *newNode = new ListNode(val, dummyHead->next);
        dummyHead->next = newNode;
        listSize++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {ListNode *newNode = new ListNode(val, nullptr);
        ListNode *cur = dummyHead;
        while(cur->next != nullptr){cur = cur->next;}
        cur->next = newNode;
        listSize++;
    }
    
    /** 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 > listSize) return;
        ListNode *newNode = new ListNode(val, nullptr);
        ListNode *cur = dummyHead;
        while(index --){cur = cur->next;}
        newNode->next = cur->next;
        cur->next = newNode;
        listSize++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {if(index >= listSize || index < 0) return;
        ListNode *cur = dummyHead;
        while(index--){cur = cur->next;}
        ListNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        listSize--; 
    }

    void printLinkedList() {
        ListNode *cur = dummyHead;
        while(cur->next != nullptr){
            cout << cur->next->val << " ";
            cur = cur->next;
        } 
        cout << endl;
    }
private:
    ListNode *dummyHead;
    int listSize;
};

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

206- 反转链表 - 双指针 (或者递归)

• 递归不谈，不喜爱递归 zzz

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *tmp = nullptr;
        while(cur != nullptr){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;  
        }
        return pre;
    }
};