2022秋招准备|牛客面试刷题链表|数据结构|面试

系列文章目录 提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加

文章目录

系列文章目录
前言
一、面试必刷TOP101？
总结

前言 【2022秋招准备|牛客面试刷题】提示：2022.8.1开始刷题，争取一天两题
一、面试必刷TOP101？

BM1 反转链表

文章图片

文章图片

ji

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* p = NULL; ListNode* c; ListNode* temp; if(pHead == NULL){ return NULL; } c = pHead; //让c指向链表的第一个元素，这样做是为了不破坏原始链表 while(c != NULL){ //这里不能是c->next ! = NULL 否则最后一个元素会忽略掉 temp = c->next; //摘下链表c的其余元素c->next = p; p = c; c = temp; } return p; //返回重新排好后的链表 } };

解题思路：本题相当于是顺序表的逆序，但涉及到了链表。本题核心是在链表的头插法，需要初始化一个空链表p，在头插法时，需要使用一个临时链表temp，另外需要保持原链表的不变性。

BM4 合并两个排序的链表

文章图片

文章图片

文章图片

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* tmp1,*tmp2; ListNode* r; //需要记录链表的尾部，方便增加元素 ListNode* head = new ListNode(0); //加一个表头，方便尾指针操作 r = head; while(pHead1!=NULL && pHead2!=NULL){ if(pHead1->val < pHead2->val){ tmp1 = pHead1->next; r->next = pHead1; pHead1 = tmp1; } else{ tmp2 = pHead2->next; r->next = pHead2; pHead2 = tmp2; } r=r->next; //让链尾指针指向最后一个元素 } //只要有其中某一个链表为空，那么直接将非空的链表复制给新链表 if(pHead1!=NULL){ r->next = pHead1; //将链表1的内容全部复制给链表3 } else{ r->next = pHead2; //将链表2的内容全部复制给链表3 }return head->next; } };

解题思路：数据结构里面的内容，之前学过，本题较为简单，题目给定的两个链表是有序的，核心在于新链表需要增加一个头指针，这样方便尾指针增加元素，最后返回的是head->next。
2022.8.1

BM6 判断链表中是否有环

文章图片

文章图片

解题思路：通过创建快慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，如果最后快指针和慢指针相遇，说明有环，否则没有环。

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { //利用两个指针（快指针fast和慢指针slow，快指针比慢指针多走两步） //如果最后快指针和慢指针相遇，那么说明有环，否则无环 ListNode* fast=head; ListNode* slow=head; if(fast==NULL) return false; while(fast!=NULL && fast->next!=NULL){ fast=fast->next->next; slow=slow->next; if(slow==fast) return true; } return false; } };

BM8 链表中倒数最后k个结点

文章图片

文章图片

解题思路：通过快慢指针，快指针先走K个节点，需要判断是否不足K个节点，然后快慢指针同时后移，直到快指针走向链尾，返回慢指针。

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* FindKthToTail(ListNode* pHead, int k) { // write code here //利用快慢指针，让快指针先走K步，然后慢指针和快指针同时后移，当快指针指向链尾 //此时返回慢指针，即是返回链表的末尾K个节点的值 ListNode* fast=pHead; ListNode* slow=pHead; for(int i=0; inext; else return NULL; } while(fast!=NULL){ fast=fast->next; slow=slow->next; }return slow; } };

2022.8.2

BM15 删除有序链表中重复的元素

文章图片

解题思路：使用快慢指针，比较两指针的值，如果相同，则删除快指针的内容。注意比较的是两个节点的值，然后删除某一个节点，使用链表中的删除节点的方法。

/** * struct ListNode { * int val; * struct ListNode *next; * }; */class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here //使用快慢指针，比较两指针的值，如果相同，则删除快指针的内容 if(head==NULL){ return NULL; } ListNode* fast; ListNode* slow; slow = head; fast = head->next; while(fast!=NULL){//快指针未指向链尾 if(fast->val!=slow->val){//这里比较的是两个节点的值 fast = fast->next; slow = slow->next; } else{ slow->next = fast->next; fast = slow->next; } } return head; } };

总结 提示：这里对文章进行总结：