牛客面试刷题_牛客刷面试题

系列文章目录

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

---

前言

提示：2022.8.1开始刷题，争取一天两题

一、面试必刷TOP101？

1. 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; //返回重新排好后的链表
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

2. 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

---

3. 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;
    
    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

4. 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;i<k;i++){
            if(fast!=NULL)
                fast=fast->next;
            else
                return NULL;
        }
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        
        return slow;  
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2022.8.2

---

5. 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

总结

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