leetcode刷题-每日更新|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; }} };


    推荐阅读