数据结构介绍: 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;
}}
};
推荐阅读
- Leetcode|LeetCode 反转链表-C++
- C++标准库|std::equal 用法
- 算法设计(从未排序的链表中删除重复项)
- 算法设计(以给定大小的组反向链表|套装2)
- c++|蓝桥杯真题(3)
- LeetCode刷题记录|LeetCode 987. 二叉树的垂序遍历
- c++指针最全总结(附源码和详细总结)
- LeetCode|LeetCode刷题笔记(279.完全平方数)
- 分治|【模拟赛|ZROI】01串(容斥,分治FFT)