leetcode刷题-每日更新|Leetcode刷题--链表（C++） leetcode|c++|链表

数据结构介绍: 1 链表由节点和指针构成；2 无法直接获取任意节点的值，必须通过指针；3 插入删除比较方便；4 很多链表问题可以用递归来解决；5 未遍历到尾指针时，无法确定链表长度。
leetcode默认链表表示方法：

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x),next(nullptr) {} };

注意：在链表操作时，特别是删除节点，会因为当前节点进行操作而导致内存或指针出现问题。有两个方法可以解决：1 尽量处理当前当前节点的下一个节点而非当前节点本身；2 是建立一个虚拟节点dummy，使其指向当前链表的头节点，这样即使原链表都被删除了，也会存在一个虚拟节点dummy存在，返回dummy->next.
leetcode 206 Reverse Linked List 方法一：保存前一节点prev，如果当前节点curr存在，则反转当前节点，再将prev和curr向后移动一步。

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while(curr) { ListNode * next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } };

方法2：递归

class Solution { public: ListNode* reverseList(ListNode* head) { if(!head || !head->next) { return head; } ListNode *temp = reverseList(head->next); head->next->next = head; head->next = nullptr; return temp; } };

leetcode 21 合并两个升序链表 【leetcode刷题-每日更新|Leetcode刷题--链表（C++）】方法1 迭代

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode * p = new ListNode(0); ListNode * L3 = p; while(l1 && l2) { if(l1->val <= l2->val) { L3->next = l1; l1 = l1->next; L3 = L3->next; } else { L3->next = l2; l2 = l2->next; L3 = L3->next; } } if(l1) L3->next = l1; if(l2) L3->next = l2; return p->next; } };

方法2 递归(代码量少)

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { //递归 if(!l1) return l2; if(!l2) return l1; if(l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1,l2->next); return l2; }} };