下载中国建设银行官网站,珠海知名网站,如何做网站内容管理,公众号怎么做教程一、移除链表元素
本题为力扣原题203
题目介绍#xff1a;
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。 列表中的节点数目范围在 0~10000内 1Node.val50 0val50 …一、移除链表元素
本题为力扣原题203
题目介绍
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 列表中的节点数目范围在 0~10000内 1Node.val50 0val50 思路利用双指针解决struct ListNode*dstNULL;struct ListNode*curhead;利用指针cur便利整个链表。
注需要考虑到要删除的是否是头节点。
让我们看看如何来实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*dstNULL;struct ListNode*curhead;while(cur){if(cur-valval){//找到了删除if(curhead){headcur-next;free(cur);curhead;}else{dst-nextcur-next;free(cur);curdst-next;}}else {dstcur;curcur-next;}}return head;
}
二、反转链表
本题为力扣原题206
题目介绍
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路利用三指针解决指针n1和n2用来交换指向至真n3用来找到下一个节点。
注需要注意的是判断指针在什么情况下为空避免利用空指针。n1最开始为空。
让我们看看如何来实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head)
{struct ListNode*n1;struct ListNode*n2;struct ListNode*n3;n1NULL;n2head;if(n2){n3n2-next;}while(n2){n2-nextn1;//往后移动n1n2;n2n3;if(n3){n3n3-next;}}return n1;
}
三、链表的中间节点
本题为力扣原题876
题目介绍
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点 思路快慢指针快指针每次走两步慢指针每次走一步当快指针到达尾部时慢指针刚好到达中间节点
让我们看看如何来实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///快慢指针
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falsthead;slowhead;while(falstfalst-next){slowslow-next;falstfalst-next-next;}return slow;
}
四、返回倒数第k个节点
题目介绍;
输入一个长度为 n 的链表设链表中的元素的值为 ai 返回该链表中倒数第k个节点。
如果该链表长度小于k请返回一个长度为 0 的链表。 思路和上面一题很相似还是用快慢指针只不过这次是让快慢指针都开始指向头节点让快指针先走k步然后慢指针和快指针在同时往后走当快指针到达尾的时候慢指针就指向了倒数第k个元素了。
注这里需要注意的是k的大小当k大于链表长度是就会溢出这里我们直接返回NULL。
让我们看看如何来实现
/*** struct ListNode {* int val;* struct ListNode *next;* };*/
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pHead, int k )
{if(pHeadNULL){return NULL;}struct ListNode*slowpHead;struct ListNode*falstpHead;int len0;while(pHead){len;pHeadpHead-next;}if(klen){return NULL;}while(k){falstfalst-next;k--;}while(falst){falstfalst-next;slowslow-next;}return slow;
}
五、合并两个有序链表
题目介绍
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路首先先考虑特殊情况当链表一为空是返回链表二链表二为空时返回链表一。然后我们开始遍历链表一和链表二比较两个指针指向链表的元素大小创建一个新链表头节点将小的元素的节点尾插到新链表上然后将较小元素的指针后移然后在比较......如果最后链表一遍历完了就可以将指向链表二的指针指向新链表的尾部最后然会新链表的头节点。
注题目时不带头节点的所以我们创建玩心链表的头节点需要销毁头指针指向头节点的下一个节点。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL){return list2;}if(list2NULL){return list1;}struct ListNode*tailNULL;struct ListNode*headNULL;headtail(struct ListNode*)malloc(sizeof(struct ListNode));while(list1list2){if(list2-vallist1-val){tail-nextlist1;tailtail-next;list1list1-next;}else{tail-nextlist2;tailtail-next;list2list2-next;} }if(list1){tail-nextlist1;}if(list2){tail-nextlist2;}struct ListNode* delhead;headhead-next;free(del);return head;
}
