力扣数据结构14天学习计划—day7

力扣141—环形链表

力扣141

相关标签：哈希表、双指针、链表

题意

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解题思路—双指针+哈希

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution 
{
public:bool hasCycle(ListNode *head) {// 法1、双指针/*ListNode* slow,* fast;fast=slow=head;// 判断条件是 fast!=nullptr&&fast->next!=nullptr// 因为，如果fast->next==NULL的话，fast指针走两步就会报错，即 NULL->next会报错// 如果fast->next为最后一个节点了（假设无环），fast走两步就会到达NULl//下一次判断循环条件时，fast为NULL就会跳出循环，从而返回false，表示无环。while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;*///法2、哈希表unordered_set uset;ListNode* node=head;while(node!=NULL){if(uset.count(node)>=1)return true;uset.insert(node);node=node->next;}return false;}
};

力扣21—合并两个有序链表

力扣21

 相关标签：递归、链表

题意

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  

解法1—递归

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

递归解析：

• 终止条件：当两个链表都为空时，表示我们对链表已合并完成。
• 如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {//递归法if(list1==nullptr)return list2;if(list2==nullptr)return list1;if(list1->val <= list2->val){list1->next = mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list1,list2->next);return list2;}}
};

 解法2—迭代

创建一个虚拟头结点，建立一个pre指针，指向结果链表中的最后一个节点。一次遍历 l1和l2两个链表，将较小节点插入到结果链表中，然后较小节点后移，pre也后移使其指向结果链表中最后一个节点。

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {// 迭代法ListNode* node1=list1,*node2=list2;ListNode* dummyHead=new ListNode(-1);   //虚拟头结点，将最终返回的结果接在它之后ListNode* pre=dummyHead; //pre指向 结果链表 中最后一个节点while(node1&&node2){if( node1->val <= node2->val ) //node1的值要小一点{//就讲node1插入到pre的后面pre->next=node1;//同时，node1和pre都要后移node1=node1->next;pre=pre->next;}else{pre->next=node2;node2=node2->next;pre=pre->next;}}if(node1)pre->next=node1;if(node2)pre->next=node2;ListNode* res = dummyHead->next;delete dummyHead;return res;}
};

力扣203—移除链表元素

力扣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) {//法1，创建一个虚拟头结点/*ListNode* dummyHead = new ListNode(0,nullptr);dummyHead->next=head;ListNode* cur = dummyHead;while(cur->next!=nullptr){if(cur->next->val==val){ListNode* del_node = cur->next;cur->next=del_node->next;delete del_node;}else{cur=cur->next;}}head=dummyHead->next;delete dummyHead;return head;*///法2，不创建虚拟头结点，考虑首节点为删除节点的情况while(head!=NULL&&head->val==val){head=head->next;}if(!head){return NULL;}ListNode* cur = head;while(cur->next!=NULL){if(cur->next->val==val){cur->next=cur->next->next;}else{cur=cur->next;}}return head;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！