武强营销型网站建设费用,互联网推广员,苏州做网站哪家比较好,dedecms收费怎么办文章目录前言一、 移除链表元素1.题目介绍2.思路3.代码二、反转链表1.题目介绍2.思路3.代码三、链表的中间结点1.题目介绍2.思路3.代码四、链表的中间结点1.题目介绍2.思路3.代码前言
以下是链表经常考的面试题#xff0c;我在这里进行归纳和讲解#xff0c;采取的是循序渐进…
文章目录前言一、 移除链表元素1.题目介绍2.思路3.代码二、反转链表1.题目介绍2.思路3.代码三、链表的中间结点1.题目介绍2.思路3.代码四、链表的中间结点1.题目介绍2.思路3.代码前言
以下是链表经常考的面试题我在这里进行归纳和讲解采取的是循序渐进的方式y一一讲解 当然需要有链表基础没有的话先看我前面的链表讲解 一、 移除链表元素
1.题目介绍
题目在力扣得的203. 移除链表元素
2.思路
本题有两种思路 1.使用带有哨兵位的头结点 2.将头结点为空时和头删时两种情况分开写 3.代码
1.带哨兵位的头节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*dummyHead(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead-nexthead;struct ListNode*prev dummyHead;struct ListNode*curhead;while(cur){struct ListNode*tempcur;if(cur-valval){struct ListNode*nextcur-next;prev-nextnext;}else{prevcur; }curcur-next; }return dummyHead-next;
}2.不带哨兵位头节点的
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prevhead;if(prevNULL){return head;}struct ListNode*curprev-next;while(cur){if(prev-valvalprev-next!NULL)//需要头删的情况且之后有元素时{prevprev-next;headprev;curprev-next;}else if(cur-valval){prev-nextcur-next;curcur-next;}else if(cur-val!val){prevcur;curcur-next;}}if(prev-valvalprev-nextNULL)//只有头节点的而且需要头删的{headNULL;return head;}return head;}二、反转链表
1.题目介绍
题目在206. 反转链表
2.思路 此题用三个指针prev保存前面得节点的地址cur保存当前的地址同时cur也是需要改变next的节点next保存cur下一个节点的地址 最后返回prev即可 3.代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode*prev,*cur,*next;prevNULL;curhead;while(cur){nextcur-next;cur-nextprev;prevcur;curnext;}return prev;
}三、链表的中间结点
1.题目介绍
题目在力扣的876. 链表的中间结点 2.思路
如果你做过数组的双指针题那么这题你就会很快的做出来如果你不能很快的理解我的做法你可以到前面的数组的刷题里面去看双指针法你就会炉火纯青了好了就算你不了解双指针法也很快的理解我的做法 我们可以用一慢指针和快指针快指针的速度是慢指针的2倍即慢指针每走一步快指针就走两步我们假设这个链表的长度为n而快指针走完这个链表时慢指针刚好就指向链表的中间的位置 3.代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){struct ListNode*slowhead;struct ListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next; }return slow;}四、链表的中间结点
1.题目介绍
题目在牛客链表中倒数第k个结点
2.思路
如果你做过我前面的一个题目那么这题就非常好理解了 我们可以搞两个指针一个slow一个fast让fast先走k步然后当fast走完时slow就是倒数第k个节点 3.代码
/*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* fastpListHead;struct ListNode* slowpListHead;while(k--){if(fastNULL){return NULL;}fastfast-next;}while(fast){fastfast-next;slowslow-next;}return slow;
}
