网站维护方法,工作内容如何创造价值,湖北建站管理系统信息,0460网站之家单链表OJ题 前言一、删除链表中等于给定值 val 的所有节点二、反转一个单链表三、返回链表的中间结点四、输出该链表中倒数第k个结点五、将两个有序链表合并六、链表的回文结构七、将链表分割成两部分八、找出第一个公共结点九、判断链表中是否有环总结 前言
在前面的博客中我… 单链表OJ题 前言一、删除链表中等于给定值 val 的所有节点二、反转一个单链表三、返回链表的中间结点四、输出该链表中倒数第k个结点五、将两个有序链表合并六、链表的回文结构七、将链表分割成两部分八、找出第一个公共结点九、判断链表中是否有环总结 前言
在前面的博客中我们知道了什么是单链表以及如何建立单链表 现在让我们来检验一下学习成果吧 提示此博客中题目均来自牛客网以及力扣网在题目中我会附带两大网站的链接大家也可以去练习一下 若有链接问题可以在评论区及时反馈 一、删除链表中等于给定值 val 的所有节点
题目链接OJ链接 提示 列表中的节点数目在范围 [0, 104] 内 1 Node.val 50 0 val 50 思路解析
代码演示
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead NULL;struct ListNode* move head;struct ListNode* tail NULL;while (move ! NULL) {if (move-val ! val) {if (tail NULL) {//如果newnode为NULL则tail等于newnode则直接将结点地址赋予tailnewhead tail move;move move-next;}else {tail-next move;move move-next;tail tail-next;}}else {struct ListNode* temp move;//新建结点保存要free的地址以免free后造成节点丢失move move-next;free(temp);}}if (tail)//如果新链表不为空则将其尾结点的next置空tail-next NULL;return newhead;}二、反转一个单链表
题目链接OJ链接 提示 链表中节点的数目范围是 [0, 5000] -5000 Node.val 5000 思路解析
代码演示
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* move1 head;struct ListNode* tail head;if (head NULL || head-next NULL) {//如果链表为空或者只有一个结点则不需要反转return tail;}struct ListNode* move2 move1-next;while (move2) {struct ListNode* temp move2-next;//保存下一个结点的地址防止后面的节点丢失move2-next move1;move1 move2;move2 temp;}tail-next NULL;//尾结点的next置空struct ListNode* newhead move1;//move1最后指向了反转链表的起始结点return newhead;
}三、返回链表的中间结点
题目链接OJ链接 提示 链表的结点数范围是 [1, 100] 1 Node.val 100 思路解析
代码演示
struct ListNode* middleNode(struct ListNode* head){struct ListNode*move1head;struct ListNode*move2head;while(move2!NULLmove2-next!NULL){//此处move2!NULL和move2-next!NULLmove1move1-next; //的位置不能交换否则会造成空指针错误move2move2-next-next;}return move1;
}四、输出该链表中倒数第k个结点
题目链接OJ链接 思路解析
代码演示
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode*move1pListHead;struct ListNode*move2pListHead;int ik;while(i0move2!NULL){//move2向后移动k位move2move2-next;i--;}if(move2NULLi0){//如果k大于链表结点数目则返回NULLreturn move2;}while(move2){move1move1-next;move2move2-next;}return move1;
}五、将两个有序链表合并
题目链接OJ链接 提示 两个链表的节点数目范围是 [0, 50] -100 Node.val 100 l1 和 l2 均按 非递减顺序 排列 思路解析
代码演示
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*move1list1;struct ListNode*move2list2;struct ListNode*newnodeNULL;struct ListNode*tailNULL;while(move1!NULLmove2!NULL){if(move1-valmove2-val){if(tailNULL){{//如果newnode为NULL则tail等于newnode则直接将结点地址赋予tailnewnodetailmove1;move1move1-next;}else{tail-nextmove1;move1move1-next;tailtail-next;}}else{if(tailNULL){//如果newnode为NULL则tail等于newnode则直接将结点地址赋予tailnewnodetailmove2;move2move2-next;}else{tail-nextmove2;move2move2-next;tailtail-next;}}}if(move1NULL){//如果链表1遍历完而链表2没有则将链表2剩余结点尾插到newnode中while(move2!NULL){if(tailNULL){//如果newnode为NULL则tail等于newnode则直接将结点地址赋予tailnewnodetailmove2;move2move2-next;}else{tail-nextmove2;move2move2-next;tailtail-next;}}}if(move2NULL){//如果链表2遍历完而链表1没有则将链表1剩余结点尾插到newnode中while(move1!NULL){if(tailNULL){//如果newnode为NULL则tail等于newnode则直接将结点地址赋予tailnewnodetailmove1;move1move1-next;}else{tail-nextmove1;move1move1-next;tailtail-next;}}}return newnode;
}六、链表的回文结构
题目链接OJ链接 思路解析
代码演示
bool chkPalindrome(struct ListNode* A) {struct ListNode* move1 A;struct ListNode* move2 A;struct ListNode* move3 A;struct ListNode* newnode NULL;struct ListNode* tail NULL;while (move2 ! NULLmove2-next ! NULL ) {//找到中间节点move1 move1-next;move2 move2-next-next;}if (move2 NULL);//如果节点个数为奇数则move1向后移动一位else {move1 move1-next;}while (move1 ! NULL) {//将后半段链表头插到newnode中if (newnode NULL) {newnode tail move1;move1 move1-next;tail-next NULL;}else {struct ListNode* temp move1-next;move1-next newnode;newnode move1;move1 temp;}}struct ListNode* cmp newnode;while (move3 ! NULL cmp ! NULL) {//比较原链表前半段和newnode是否相同if (move3-val ! cmp-val) {return 0;}else {move3 move3-next;cmp cmp-next;}}return 1;
}七、将链表分割成两部分
题目链接OJ链接 思路解析 代码演示
ListNode* partition(ListNode* pHead, int x) {struct ListNode*head1(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*head2(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*tail1head1;struct ListNode*tail2head2;struct ListNode*movepHead;while(move){if(move-valx){tail1-nextmove;movemove-next;tail1tail1-next;}else{tail2-nextmove;movemove-next;tail2tail2-next;}}tail2-nextNULL;//将尾指针的next置空tail1-nexthead2-next;struct ListNode*temp1head1;struct ListNode*temp2head2;head1head1-next;//指针指向头结点的下一节点free(temp1);//释放掉创建的头结点free(temp2);return head1;}八、找出第一个公共结点
题目链接OJ链接 注意 函数返回结果后链表必须 保持其原始结构 。 思路解析
代码演示
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *move1headA;struct ListNode *move2headB;int len11,len21;while(move1){//得到链表A的长度move1move1-next;len1;}while(move2){//得到链表B的长度move2move2-next;len2;}int kabs(len1-len2);//取相减的绝对值struct ListNode *moveAheadA;struct ListNode *moveBheadB;if(len1len2){//较长的链表走k步while(k--){moveAmoveA-next;}}if(len1len2){while(k--){moveBmoveB-next;}}while(moveAmoveB){if(moveAmoveB)return moveA;//若地址相同则返回moveAmoveA-next;moveBmoveB-next;}return NULL;九、判断链表中是否有环
题目链接OJ链接 提示 链表中节点的数目范围是 [0, 104] -105 Node.val 105 pos 为 -1 或者链表中的一个 有效索引 。 思路解析
代码演示
bool hasCycle(struct ListNode *head) {struct ListNode*move1head;struct ListNode*move2head;while(move1move2move2-next){//此处move2和move2-next的顺序不可交换move1move1-next; //否则会导致空指针错误move2move2-next-next;if(move1move2)return true;}return false;
}总结
这九道单链表OJ都是我见过的很经典的题型 在这里为大家分享一下 希望有更多的人能够通过这些题目更好地掌握单链表相关的知识
