链表理论基础链表是通过指针串联在一起的线性结构数据域 指针域。指针域存放指向下一个节点的指针最后一个节点的指针域指向 null。入口节点即头结点head。链表的类型单链表双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。循环链表链表首尾相连约瑟夫环问题。链表的存储方式数组是连续分布的但链表不是连续分布的。链表是通过指针域的指针链接节点。链表的定义struct ListNode { int val; // 数据域 ListNode *next; // 指针域 ListNode(int x) : val(x), next(NULL) {} // 构造函数 };如果不自己构造函数建立节点过程会更复杂一点。ListNode* head new ListNode(); head-val 5;链表的操作删除节点把 C 节点的指针域指向 E 节点C 手动释放 D 节点内存其他语言自动释放。添加节点让 F 指针域指向 D 节点C 再指向 F 节点。链表只能一个节点一个节点的向后找寻所以要先把 F 接上 D再把 C 接上 F。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) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { while (head ! NULL head-val val) { ListNode *temp head; head head-next; delete temp; } ListNode *cur head; while (cur ! NULL cur-next ! NULL) { if (cur-next-val val) { ListNode *temp cur-next; cur-next cur-next-next; delete temp; } else { cur cur-next; } } return head; } };while 是因为可能需要多次操作比如 val 11 1 2 3……temp 是为了标记需要删除的节点地址当指针移动后原来的位置会丢失。设置一个虚拟头结点在进行删除操作。方式统一设置虚拟头节点。/** * 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 *dummyHead new ListNode(0); dummyHead-next head; ListNode *cur dummyHead; while (cur-next ! NULL) { if (cur-next-val val) { ListNode *temp cur-next; cur-next cur-next-next; delete temp; } else { cur cur-next; } } head dummyHead-next; delete dummyHead; return head; } };因为虚拟头节点一定是存在的所以说不用检验 cur ! NULL头节点在最后需要重新确定dummyHead-next 就是头节点。由于我用的是 C所以应当清理被删节点所占内存。还有一个递归的方法class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 基础情况空链表 if (head nullptr) { return nullptr; } // 递归处理 if (head-val val) { ListNode* newHead removeElements(head-next, val); delete head; return newHead; } else { head-next removeElements(head-next, val); return head; } } };707. 设计链表力扣题目链接题意在链表类中实现这些功能get(index)获取链表中第 index 个节点的值。如果索引无效则返回 -1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index, val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果 index 小于 0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。参考代码class MyLinkedList { public: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; MyLinkedList() { dummyHead new ListNode(0); size 0; } int get(int index) { if (index gt; (size - 1) || index lt; 0) { return -1; } ListNode *cur dummyHead-gt;next; while (index--) { cur cur-gt;next; } return cur-gt;val; } void addAtHead(int val) { ListNode *newNode new ListNode(val); newNode-gt;next dummyHead-gt;next; dummyHead-gt;next newNode; size; } void addAtTail(int val) { ListNode *cur dummyHead; ListNode *newNode new ListNode(val); while (cur-gt;next ! NULL) { cur cur-gt;next; } cur-gt;next newNode; size; } void addAtIndex(int index, int val) { if (index gt; size) return; if (index lt; 0) index 0; ListNode *cur dummyHead; ListNode *newNode new ListNode(val); while (index--) { cur cur-gt;next; } newNode-gt;next cur-gt;next; cur-gt;next newNode; size; } void deleteAtIndex(int index) { if (index gt; (size - 1) || index lt; 0) { return; } ListNode *cur dummyHead; while (index--) { cur cur-gt;next; } ListNode *tmp cur-gt;next; cur-gt;next cur-gt;next-gt;next; delete tmp; tmp NULL; size--; } void printListNode() { ListNode* cur dummyHead; while (cur-gt;next ! NULL) { cout lt;lt; cur-gt;next-gt;val lt;lt; ; cur cur-gt;next; } cout lt;lt; endl; } private: int size; ListNode 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); */QA1. 什么时候 cur dummyHead什么时候是 cur dummyHead-next当在寻找所对应的值的时候用 dummyHead-next因为其他增添、删除的时候必须有被删项前一项的地址。如果不好理解可以带入 index 0 想一下。2. 边界值是 size 还是 size - 1size - 1 的情况是对已有的链表进行读值、操作。size 是增添的时候可以在链表末尾增添值。注意事项size 要跟随增删及时变化。C 删除元素时要先保留地址再连接。temp NULL 是因为 tmp 并非就是 NULL可能变成了野指针。206. 反转链表力扣题目链接题意反转一个单链表。示例输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL双指针法双指针法其实很好理解1. 为什么一定是双指针呢因为在链表指向转换的时候要留存前一个元素的位置而我们是逆着新链表的链接方向进行操作的。我们知道链表没办法逆向操作让 pre cur即可实现位移。2. 那为什么要有一个 tmp 呢因为指向关系转换时会丢失下一个的位置为了让 cur 进行位移这样两个指针循环位移即可反转链表。/** * 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 *pre NULL; ListNode *cur head; while (cur ! NULL) { ListNode *tmp cur-next; cur-next pre; pre cur; cur tmp; } return pre; } };递归做法class Solution { public: ListNode* reverse(ListNode* pre, ListNode* cur) { if (cur NULL) return pre; ListNode* temp cur-next; cur-next pre; return reverse(cur, temp); } ListNode* reverseList(ListNode* head) { return reverse(NULL, head); } };递归就是一直调用直到达成条件。每一次进入 reverse 里面就是扭转箭头方向这里不用利用 temp 交换了直接将 temp 带入循环到 cur 到 null。