1.题目：203. 移除链表元素
链接：https://leetcode-cn.com/problems/remove-linked-list-elements/
方法1：递归：递归函数定义为当前节点所指向的链表中无node.val==v的情况
class Solution {
public:
ListNode* removeElements(ListNode* h, int v) {
if(h==nullptr)return nullptr;
h->next=removeElements(h->next,v);
if(h->val==v)return h->next;
return h;
}
};
方法2：迭代:定义一个头结点固定指向这个链表，然后再通过一个指针遍历链表删除node.val==v的情况
class Solution {
public:
ListNode* removeElements(ListNode* h, int v) {
if(h==nullptr)return nullptr;
ListNode * head= new ListNode(0,h);//初始化 head-next=h
ListNode * ans=head;
while(ans->next!=nullptr){
if(ans->next->val==v){
ans->next=ans->next->next;
}
else {
ans=ans->next;
}
}
return head->next;
}
};
2.合并两个有序链表
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
思路1：递归：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==nullptr)return l2;
if(l2==nullptr)return l1;
if(l1->val<l2->val) {
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}
else {
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}
}
};
思路2：迭代：定义一个头结点，然后进行类似双指针的操作迭代即可
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head=new ListNode(0);
ListNode * ans =head;
while(l1!=nullptr&&l2!=nullptr){
if(l1->val<l2->val){
ans->next=l1;
l1=l1->next;
// l2=l2->next;
ans=ans->next;
}
else {
ans->next=l2;
// l1=l1->next;
l2=l2->next;
ans=ans->next;
}
}
l1==nullptr ? ans->next=l2:ans->next=l1;
return head->next;
}
};
- 环形链表
链接：https://leetcode-cn.com/problems/linked-list-cycle/
思路1:哈希表，unordered_map或者unorderde_set 记录走过的点
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> m;
while(head!=nullptr){
if(m.count(head))return true;
m.insert(head);
head=head->next;
}
return false;
}
};
思路2：快慢指针，快指针一次移动两个节点，慢指针一次移动一个，当两个指针在同一个环内时必然会碰撞。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode * a=head, *b =head;
while(a!=nullptr&&b!=nullptr){
a=a->next;
if(a!=nullptr)
a=a->next;
b=b->next;
if(a==b&&a!=nullptr)return true;
}
return false;
}
};