微商手机网站制作公司,wordpress京东客,海南新闻在线观看,专做动漫的网站以下题目建议大家先自己动手练习#xff0c;再看题解代码。这里只提供一种做法#xff0c;可能不是最优解。
1. 移除链表元素#xff08;OJ链接#xff09;
题目描述#xff1a;给一个链表的头节点 head 和一个整数 val #xff0c;删除链表中所有满足值等于 val 的节点…以下题目建议大家先自己动手练习再看题解代码。这里只提供一种做法可能不是最优解。
1. 移除链表元素OJ链接
题目描述给一个链表的头节点 head 和一个整数 val 删除链表中所有满足值等于 val 的节点并返回新的头节点 。
解法遍历链表依次比对结点的值和val是否相等相等则删除不相等则更新指针指向继续遍历。
这里需要分两种情况来讨论一是链表结点的值都等于val二是链表结点的值不都等于val。
struct ListNode* removeElements(struct ListNode* head, int val)
{//全部结点的值都等于val或前面部分结点相等while(headhead-valval){headhead-next;}//删除全部结点后head为空或者链表本身就为空链表if(!head){return NULL;}struct ListNode* curhead;while(cur-next){//cur的下一个结点值等于val则删除下一个if(cur-next-valval){cur-nextcur-next-next;}//不相等则cur后移一步else{curcur-next;}}return head;
}无论链表结点中是什么样的值当进行完第一个while循环后如果head不是NULL那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur-next-valval这样不需要保留cur的前一个结点因为cur本身就是前一个结点可能删除的结点的前一个结点。
2. 反转链表OJ链接
题目描述给定单链表的头节点 head 反转链表并返回反转后的链表的头节点。
我们所要做的操作如下图 如果链表为NULL直接返回空即可。链表不为空则需要反转。
以上图链表为例本题解法如下图所示。
当n2为空时循环结束。
题解代码如下
struct ListNode* reverseList(struct ListNode* head)
{if(headNULL){return NULL;}struct ListNode* prevNULL;struct ListNode* curhead;struct ListNode* nexthead-next;while(cur!NULL){cur-nextprev;prevcur;curnext;if(next){nextnext-next;}}return prev;
}注意题解中的prevcur和next指针分别对应图中的n1n2n3。最后一步时n3为NULL所以需要加判断语句。
3. 链表的中间结点OJ链接
题目描述给定单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。
如果链表结点个数为奇数返回中间结点如果结点数为偶数返回第二个结点。比如有六个结点则返回第四个结点。
解法快慢指针法。指的是一个指针走的步数多一个指针走的步数少。此题快指针走两步慢指针走一步。当快指针走到NULL或最后一个结点时链表结点数为偶数或奇数慢指针指向的结点即为中间结点。
题解代码如下
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fasthead,*slowhead;while (fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;}return slow;
}4. 合并两个有序链表OJ链接
题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解法创建两个指针变量分别指向两个链表的头依次比较结点的值值小的结点链接到新链表的尾依次遍历链表其中一个链表走完后将剩余的链表链接到新链表的尾即可。
示例 题解代码如下
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}//分别指向两个链表的头结点ListNode *p1 list1, *p2 list2;//phead为新链表的头ptail为新链表的尾ListNode *phead NULL, *ptail NULL;//两个链表都没有遍历完while (p1 p2) {if (p1-val p2-val) {//链接的是第一个结点if (phead NULL) {phead ptail p1;p1 p1-next;} else {ptail-next p1;ptail ptail-next;p1 p1-next;}} else {//链接的是第一个结点if (phead NULL) {phead ptail p2;p2 p2-next;} else {ptail-next p2;p2 p2-next;ptail ptail-next;}}}//链表1没有走完if (p1) {ptail-next p1;}//链表2没有走完if (p2) {ptail-next p2;}return phead;
}5. 返回倒数第k个结点OJ链接
题目描述给定一个单链表的头结点head找出单向链表中倒数第 k 个节点。返回该节点的值。
此题和第三题类似。解法依旧是快慢指针法。
解法快指针先走k步然后和慢指针一起走快指针走到NULL时慢指针指向的结点就是倒数第k个结点。 原理快指针先走k步使得两个指针间隔为k。再一起以相同速度走最后两个指针间隔依旧是k。
题解代码如下
int kthToLast(struct ListNode* head, int k)
{struct ListNode* fasthead,*slowhead;while(k--){fastfast-next;}while(fast){fastfast-next;slowslow-next;}return slow-val;
}这里就先介绍这五个题的做法大家可以试试用别的做法看是否可以做出来噢。
