203.移除链表元素|707.设计链表|206.反转链表

/** * 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) {} * }; */class Solution {public:    ListNode* removeElements(ListNode* head, int val) {        // ListNode* virtPoint = (ListNode*)malloc(sizeof(ListNode));        ListNode* virtPoint = new ListNode(0);        virtPoint -> next = head;         ListNode* p1 = virtPoint, *p2 = head, *q = nullptr;        // ListNode* p2 = head -> next == null ? null : head -> next;        while (p2 != NULL) {            if (p2 -> val == val) {                q = p2;                p1 -> next = p2 -> next;                p2 = p2 -> next;                delete q;                // p1 = p2;这里应该做条件判断                // p2 = p2 -> next;                           }             else {                p1 = p2;                p2 = p2 -> next;            }        }        return virtPoint -> next;    }};

• 707.设计链表
  • 注意结构体的定义以及私有变量和对象的初始化
  • 将指针delete后，不要忘记赋值为nullptr,否则tmp指针将会指向随机空间而不是空

    class MyLinkedList {public://结点结构体定义    struct LinkedNode {        int val;        LinkedNode* next;        LinkedNode(int val) : val(val), next(nullptr) {}    };//初始化链表    MyLinkedList() {        dummyHead = new LinkedNode(0);        size = 0;    }        int get(int index) {        if (index  (size - 1))  return -1;        LinkedNode* cur = dummyHead -> next ;        for (int i = index; i > 0; i--) {            cur = cur -> next;        }        return cur -> val;    }        void addAtHead(int val) {        LinkedNode* newNode = new LinkedNode(val);        newNode -> next = dummyHead -> next;        dummyHead -> next = newNode;        size++;    }        void addAtTail(int val) {        LinkedNode* newNode = new LinkedNode(val);        LinkedNode* cur = dummyHead;        while (cur -> next != nullptr) {            cur = cur -> next;        }        cur -> next = newNode;        // newNode -> next = nullptr;        size++;    }        void addAtIndex(int index, int val) {        if (index > size)  return;        if (index  next;        }        newNode -> next = cur -> next;        cur -> next = newNode;        size++;    }        void deleteAtIndex(int index) {        if (index = size) return;        LinkedNode* cur = dummyHead;        LinkedNode* tmp = nullptr;        while (index--) {            cur = cur -> next;        }        tmp = cur -> next;        cur -> next = cur -> next -> next;        delete tmp;        size--;    }private :    int size;    LinkedNode* dummyHead;};/** * 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.反转链表
    • 学习思路如下图，双指针

      /** * 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) {} * }; */class Solution {public:    ListNode* reverseList(ListNode* head) {        ListNode* slow = nullptr;        ListNode* quick = head;        ListNode* tmp = nullptr;//用于存储快指针的next        while (quick) {            tmp = quick -> next;            quick -> next = slow;            slow = quick;            quick = tmp;        }        return slow;    }};