网页此站点不安全,360免费建站系统,网站建设包括备案吗,做房产中介网站学完了单链表之后#xff0c;我们对其基本结构已经有了一定的了解#xff0c;接下来我们通过一些题目强化对链表的理解#xff0c;同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。 目录
题目一.876. 链表的中间结点 - 力扣#xff08;LeetCode#x… 学完了单链表之后我们对其基本结构已经有了一定的了解接下来我们通过一些题目强化对链表的理解同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。 目录
题目一.876. 链表的中间结点 - 力扣LeetCode
题目二21. 合并两个有序链表 - 力扣LeetCode
题目三203. 移除链表元素 - 力扣LeetCode
题目四 206. 反转链表 - 力扣LeetCode
题目五141. 环形链表 - 力扣LeetCode
题目六 142. 环形链表 II - 力扣LeetCode 题目一.876. 链表的中间结点 - 力扣LeetCode
给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 我们一起来思考一下这道题目返回链表的中间结点。我们先来了解一种新思路快慢指针我们定义两个指针一个快指针一个慢指针。每次快指针走两步慢指针走一步。我们来看一下演示过程 一个中间结点情况 两个中间结点情况 通过演示过程我们可以清楚的看到
如果是奇数结点当fast指向尾结点slow返回中间结点。如果是偶数结点当fast指向空时越过尾结点slow返回中间结点。
总结以上规律应在当 fast遇到或越过尾节点时跳出循环并返回 slow 即可。
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}
题目二21. 合并两个有序链表 - 力扣LeetCode
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
我们要返回一个升序的新链表那么我们可以借助一个头指针将list1和list2进行比较值小的尾插放入新的链表中再用头指针指向新的链表就可以。
在题目中注意判断list1为空list2为空是怎么办
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode*headNULL,*tailNULL;// 处理特殊情况if(list1NULL)return list2;if(list2NULL)return list1;while(list1list2){if(list1-vallist2-val){if(tailNULL)tailheadlist1;else{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(tailNULL)tailheadlist2;else{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;return head;
}
题目三203. 移除链表元素 - 力扣LeetCode
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 思路一我们定义一个指针让这个指针移动从而去寻找链表中和val相等的值要是遇到就把它释放掉然后把上一个结点和释放掉后的下一个结点连接起来最后返回头结点head就可以。但这个思路有什么问题我们想一想如果头结点就需要释放呢那我们就要把返回的头结点此时后移注意考虑这个情况 大家可以自己思考一下再参考下面代码。
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*prevNULL,*curhead;while(cur){if(cur-valval){if(curhead){headcur-next;free(cur);curhead;//curhead-next错误}else{prev-nextcur-next;free(cur);curprev-next;}}else{prevcur;curcur-next;}}return head;
}
思路二我们定义一个新的结点当指针指向的值不等于val值的时候把结点连接到新结点上。这样返回的新的头结点就是一个没有val值的链表。 大家可以自己思考一下再参考下面代码。
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* curhead;struct ListNode* tailNULL,*newnodeNULL;while(cur){if(cur-valval){struct ListNode* nodecur;curcur-next;free(node);}else{if(tailNULL){newnodetailcur;}else{tail-nextcur;tailtail-next;}curcur-next;}}if(tail)tail-nextNULL;return newnode;
}
题目四 206. 反转链表 - 力扣LeetCode
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
还记得之前写的线性表头插吗我们发现头插和输入的顺序刚好相反那我们把这个思想用在这道题目上我们把链表的值头插到新的一个链表中返回头插后的链表的头结点。 struct ListNode* reverseList(struct ListNode* head) {struct ListNode* curhead;struct ListNode* newheadNULL;while(cur){struct ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}return newhead;
}
题目五141. 环形链表 - 力扣LeetCode
给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。
这个题目超级有意思检查链表里有没有环还记得我们的快慢指针吗如果有环的话快指针肯定先入环慢指针如果在环中和快指针相遇了说明有环如果没有相遇说明无环。
大家肯定有一个问题为什么有环就一定可以追上我们一起分析一下。当slow进环后fast开始追击假设它们之间的距离为N那么走一次它们之间的距离变为N-1下一次为N-2N-3,......3210最后它们之间的距离就是0。所以只要有环它们一定会相遇。
bool hasCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead;while(fastfast-next)//快指针将到达链表尾部该链表不为环形链表{slowslow-next;fastfast-next-next;if(slowfast)return true;}return false;
}
题目六 142. 环形链表 II - 力扣LeetCode
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
这个题目其实有点数学题的意思我们来分析一下假设起点到入口点的距离是L环的周长是C入口点到相遇点距离是X我们已经分析过slow进环后一圈内fast必追上slow那么slow的距离就是LXfast的距离是Ln*CXL可能很长导致fast已经在环里走路不止一圈slow才进入所以fast是n*C那么我们已知fast走的距离是slow的两倍这是快慢指针的定义所以我们列出式子2LXLn*CX解出Ln-1)*CC-X.也就是说一个指针从起点走另一个从相遇点走他们会在入口点相遇。 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode* meetslow;while(head!meet){meetmeet-next;headhead-next;}return meet;}}return NULL;
}
今天的分享就到这里大家有哪里不懂的可以私信我或在评论区讨论大家可以把这些题目作为链表的练习题目希望对大家的编程和数据结构有帮助
