木材 技术支持 东莞网站建设,php网站开发待遇,无忧建站网,软件上市公司排名本篇文章主要是对力扣和牛客网上一些经典的和链表有关的笔试题的总结归纳#xff0c;希望对你有所帮助。 目录
一、移除链表元素
1.1 问题描述
1.2 思路一
1.2.1 分析
1.2.2 代码
1.3 思路二
1.3.1 分析
1.2.3 思路三
1.3 代码实现
1.3.1 思路1的代码
1.3.2 思路2的… 本篇文章主要是对力扣和牛客网上一些经典的和链表有关的笔试题的总结归纳希望对你有所帮助。 目录
一、移除链表元素
1.1 问题描述
1.2 思路一
1.2.1 分析
1.2.2 代码
1.3 思路二
1.3.1 分析
1.2.3 思路三
1.3 代码实现
1.3.1 思路1的代码
1.3.2 思路2的代码
二、链表的中间结点
2.1 问题描述
2.2 思路一
2.2.1 分析 2.2.2 代码
2.3 思路二
2.3.1 分析 2.3.2 代码
三、链表中倒数第k个结点
3.1 问题描述
3.2 思路一
3.2.1 分析
3.2.2 思路
3.3 思路二
3.3.1 分析
3.3.2 代码
四、反转链表
4.1 问题描述
4.2 思路一
4.2.1 分析
4.2.2 代码
4.3 思路二
4.3.1 分析
4.3.2 代码
五、合并两个有序链表
5.1 问题描述
5.2 思路一
5.2.1 分析
5.2.2 代码
5.3 思路二
5.3.1 分析
5.3.2 代码
六、链表分割
6.1 问题描述
6.2 思路
6.2.1 分析
6.2.2 代码
七、链表的回文结构
7.1 问题描述
7.2 思路
7.2.1 分析
7.2.2 代码
八、相交链表
8.1 问题描述
8.2 思路
8.2.1 分析
8.2.2 代码 一、移除链表元素
1.1 问题描述
删除链表中等于给定值 val 的所有结点。原题链接https://leetcode.cn/problems/remove-linked-list-elements/description/1.2 思路一
1.2.1 分析 双指针的方式cur中存储的数据如果等于val就让cur的前一个结点prev的指针指向cur的后一个结点然后把cur的空间释放了再继续向后遍历。 在这种情况下我们需要考虑头结点的值就等于val的情况即下例
1.2.2 代码
struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur head;struct ListNode* prev NULL;while(cur){if(head-valval){head head-next;free(cur);cur head;}else {if(cur-valval){prev-next cur-next;free(cur);cur prev-next;}else{prev cur;cur cur-next;}}}return head;
}
1.3 代码2
struct ListNode* removeElements(struct ListNode* head, int val){if(headNULL){return NULL;}struct ListNode* cur head;struct ListNode* newhead,*tail;newhead tail NULL;while(cur){if(cur-val!val){if(tailNULL){newhead tail cur;}else {tail-next cur;tail cur;}cur cur-next;}else {struct ListNode* next cur-next;free(cur);cur next;}}if(tail){tail-next NULL;}return newhead;}
1.4 代码3
struct ListNode* removeElements(struct ListNode* head, int val){if(headNULL){return NULL;}struct ListNode* guard,*tail;guard tail (struct ListNode*)malloc(sizeof(struct ListNode));guard-next NULL;struct ListNode* cur head;while(cur){if(cur-val!val){tail-next cur;tail cur;cur cur-next;}else {struct ListNode* next cur-next;free(cur);cur next;}}tail-next NULL;struct ListNode* p guard-next;free(guard);return p;}
二、链表的中间结点
2.1 问题描述
oj链接876. 链表的中间结点 - 力扣LeetCode 2.2 思路一
2.2.1 分析 我们可以使用快慢指针快慢指针都从head即头结点开始慢指针slow每次走一步快指针fast每次走两步对于此题链表中结点的个数为偶数个和为奇数个时的结束条件不同。 如果链表的结点个数是奇数个那么当快指针走到最后一个结点时慢指针正好到达中间结点。 如果链表的结点个数是偶数个那么就有两个中间结点题中说明如果有两个中间结点返回第二个中间结点。当快指针走到最后一个结点的下一个即走到空时慢指针正好到达中间结点。 2.2.2 代码
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow head,*fast head;while(fastfast-next){slow slow-next;fast fast-next-next;}return slow;
}
2.3 思路二
2.3.1 分析 通过遍历求出链表结点的总个数然后得到中间结点的位置再次遍历找到中间结点返回。 2.3.2 代码
struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur head;int count 0;while(cur){count;cur cur-next;}int middle count/2;cur head;while(middle--){cur cur-next;} return cur;
}
三、链表中倒数第k个结点
3.1 问题描述
牛客链接链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 3.2 思路一
3.2.1 分析 使用快慢指针慢指针slow和快指针fast之间距离相差k然后同步移动当快指针fast移动到空的时候慢指针指向的就是倒数第k个结点。 3.2.2 思路
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast pListHead;struct ListNode* slow pListHead;while(k--){if(fast!NULL)fast fast-next;elsereturn NULL;}while(fast){slow slow-next;fast fast-next;}return slow;}
3.3 思路二
3.3.1 分析 求出整个链表的结点个数倒数第k个结点就是从头结点向后走n-k次。
3.3.2 代码
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {int count 0;struct ListNode* cur pListHead;while(cur){count;cur cur-next;}if(kcount){return NULL;}int x count - k;cur pListHead;while(x--){cur cur-next;}return cur;}
四、反转链表
4.1 问题描述
oj链接206. 反转链表 - 力扣LeetCode 4.2 思路一
4.2.1 分析 取链表中的结点头插到一个新链表上然后返回新链表的头结点。 4.2.2 代码
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur head;struct ListNode* newhead NULL;struct ListNode* next NULL;while(cur){next cur-next;cur-next newhead;newhead cur;cur next;}return newhead;
} 4.3 思路二
4.3.1 分析 把链表的指针翻转让每一个指针指向他的前一个。 4.3.2 代码
struct ListNode* reverseList(struct ListNode* head){if(headNULL)return NULL;struct ListNode* cur head,*prev NULL;struct ListNode* next cur-next;while(cur){next cur-next;cur-next prev;prev cur;curnext;}return prev;}
五、合并两个有序链表
5.1 问题描述
oj链接21. 合并两个有序链表 - 力扣LeetCode 5.2 思路一
5.2.1 分析 依次比较两个链表的结点取出小的结点尾插到一个新链表上当有一个链表走到空时直接将剩下的那个链表链接到新链表上。
在此方法中我们需要注意
需要单独考虑到两个链表中有空链表的情况。在尾插时考虑新链表为空的情况需要单独处理。5.2.2 代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* n1 list1,*n2 list2;struct ListNode* newhead NULL,*tail NULL;if(n1NULL){return n2;}if(n2NULL){return n1;}while(n1n2){if(n1-valn2-val){if(newhead NULL){newhead tail n1; }else{tail-next n1;tail tail-next;}n1 n1-next;;}else{if(newhead NULL){newhead tail n2; }else{tail-next n2;tail tail-next;}n2 n2-next;;}}if(n1){tail-next n1;}if(n2){tail-next n2;}return newhead;}
5.3 思路二
5.3.1 分析 思路二其实是思路一的改进思路二中引用了带哨兵位的头结点的链表这样就不需要再单独处理尾插时新链表为空和两个链表中有链表为空的问题在这里创建哨兵位的头结点主要用动态开辟的方式当不再使用时需要释放。 5.3.2 代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* n1 list1,*n2 list2;struct ListNode* newhead (struct ListNode*)malloc(sizeof(struct ListNode));newhead-next NULL;struct ListNode* tail newhead;while(n1n2){if(n1-valn2-val){tail-next n2;n2 n2-next;tail tail-next;}else{tail-next n1;n1 n1-next;tailtail-next;}}if(n1){tail-next n1;}if(n2){tail-next n2;}struct ListNode* next newhead-next;free(newhead);return next;}
六、链表分割
6.1 问题描述
oj链接链表分割_牛客题霸_牛客网 (nowcoder.com) 6.2 思路
6.2.1 分析 新建两个链表把小于x的尾插到其中一个链表大于等于x的尾插到另一个链表然后把这两个链表链接起来。注意我们新建的两个链表最好用带哨兵位的头结点的链表这样可以避免我们在尾插时需要对空单独分析的问题。 6.2.2 代码
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* lesshead NULL,*lesstail NULL;struct ListNode* greaterhead NULL,*greatertail NULL;struct ListNode* cur pHead;lesshead lesstail (struct ListNode*)malloc(sizeof(struct ListNode));greaterhead greatertail (struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur-valx){lesstail-next cur;lesstaillesstail-next;}else {greatertail-next cur;greatertailgreatertail-next;}cur cur-next;}greatertail-nextNULL;lesstail-next greaterhead-next;free(greaterhead);struct ListNode* p lesshead-next;free(lesshead);return p;}
};七、链表的回文结构
7.1 问题描述
oj链接链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 7.2 思路
7.2.1 分析 在这里我们提供一个思路首先找到中间结点然后将中间结点包括中间结点后面的部分逆置然后将前半段和后半段进行比较。 在之前的题目中我们已经写过了找中间结点以及链表反转的代码在这里直接拷贝。 7.2.2 代码
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow head,*fast head;while(fastfast-next){slow slow-next;fast fast-next-next;}return slow;
}struct ListNode* reverseList(struct ListNode* head){if(headNULL)return NULL;struct ListNode* cur head,*prev NULL;struct ListNode* next cur-next;while(cur){next cur-next;cur-next prev;prev cur;curnext;}return prev;}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* n2 reverseList(mid);struct ListNode* n1 A;while(n2n1){if(n1-val!n2-val){return false;}n2 n2-next;n1 n1-next;}return true;
}
};
八、相交链表
8.1 问题描述
oj链接160. 相交链表 - 力扣LeetCode 8.2 思路
8.2.1 分析 分别求两个链表的长度长的链表先走差距步然后再同时走第一个地址相同的指针就是交点。 8.2.2 代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* n1 headA;struct ListNode* n2 headB;int x1 0;int x2 0;while(n1){x1;n1 n1-next;}while(n2){x2;n2 n2-next;}if(n1!n2)return NULL;int x abs(x1-x2);struct ListNode * shortList headA,*longList headB;if(x1x2){shortList headB;longList headA;}while(x--){longList longList-next;}while(longList!shortList){longList longList-next;shortList shortList-next;}return longList;}
