2024-05-25 22:53 联发科技_智慧产品软件开发部_Android BSP

关注

嵌入式软件常用面试题汇总之 C/C++ 语言相关(4)

C/C++之常考链表相关基础编程题汇总

嵌入式的笔试中编程题大部分会是基础的链表操作题，以下挑几道当时做过比较重点经典的，掌握了基本就能通关，参考的解法都是几年前自己做的了，也欢迎各位优化指正！

1.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：false

解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10⁴]
-10⁵ <= Node.val <= 10⁵
pos 为 -1 或者链表中的一个 有效索引 。

解法参考：

/**
 * 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) 
    {
        if(head == NULL || head->next == NULL )
        {
            return false;
        }
        ListNode *fast = head;
        ListNode *slow = head;
        //此处有一个细节，判断(fast->next->next) != NULL之前需要对fast->next进行判断，不然会报错
        while(fast->next != NULL && (fast->next->next) != NULL )
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                return true;
            }
        }
        return false;
    }
};

2.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = []

输出：[]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解法参考：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
/*方法一：直接递归 */
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL) return list2;
        if(list2==NULL) return list1;
        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else
        {
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};
       
/*方法二：双指针，类似于之前的数组合并 */     
        // if(list1==NULL) return list2;
        // if(list2==NULL) return list1;
        // ListNode* result = new ListNode;  //注意不能返回局部变量，所以要申请地址
        // ListNode* p = result;               //借助P来完成遍历的操作
        // ListNode* l1 = list1;
        // ListNode* l2 = list2;
        // while(l1!=NULL && l2!= NULL)
        // {   
        //    if(l1->val <= l2->val )
        //    {
        //        p->next = l1;
        //        p = p->next;
        //        l1 = l1->next;
        //    }else if(l1->val > l2->val )
        //    {
        //        p->next = l2;
        //        p = p->next;
        //        l2 = l2->next;
        //    }     
        // }
        // if(l1 == NULL)
        // {
        //     p->next = l2;
        //     return result->next;
        // }else if(l2 == NULL)
        // {
        //     p->next = l1;
        //     return result->next;
        // }
        // return result->next;
/*                                           */

3.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1

输出：[]

示例 3：

输入：head = [1], n = 1

输出：[]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解法参考：

/*方法：
第一种：用一个哈希表，key值是顺序，遍历一遍链表把结点都顺序存到哈希表里面，最后再直接拿到 n-k+1的那个结点即可
第二种：不用哈希表，但是要遍历两次链表，第一计算总长度，第二次去取对应位置的值
第三种：快慢指针，快指针先走k-1个节点，然后和慢指针一起每次走一步，当快指针到尾部时慢指针即为所要找的结点
然后注意这道题是删掉这个结点，所以变通一下
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        if(head->next == NULL)
        {
            head = NULL;
            return head;
        } 
            ListNode* fast = head;
            ListNode* slow = head;
            for(int i = 0 ; i < n ; i++)//这里想让slow是要删除的前一个，但是要注意边界
            {                
                fast = fast->next;
            }
            if(fast == NULL) return head->next; 
            while(fast->next != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
            //此时slow为要删的前一个
            ListNode* pos = slow->next;
            slow->next = pos->next;
            return head;
    }
};

4.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

解法参考(发现以前自己写了一堆if else.....有空再优化看看解法)：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* CreatNode(int data){
    struct ListNode* NewNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    NewNode->next=NULL;
    NewNode->val=data;
    return NewNode;
}
void InsertNode(struct ListNode* HeadNode,int data){
    struct ListNode* NewNode = CreatNode(data);
    struct ListNode* PosNode = HeadNode;
    while(PosNode->next!=NULL){
        PosNode=PosNode->next;       
    }   
    PosNode->next=NewNode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int Posflag=0;
char Addflag=0;
int data=0;
struct ListNode* HeadNode = CreatNode(0);
while(1){
    if(l1!=NULL&&l2!=NULL){
       if(l1->val+l2->val+Addflag<10){
               data=l1->val+l2->val+Addflag;
               Addflag=0;
               l1=l1->next;
               l2=l2->next;               
              InsertNode(HeadNode,data);
           }else if(l1->val+l2->val+Addflag>=10){
            data=l1->val+l2->val+Addflag-10;
            Addflag=1;        
            l1=l1->next;
            l2=l2->next; 
            InsertNode(HeadNode,data);        
       }
    }else if(l1!=NULL&&l2==NULL){
        if(l1->val+Addflag<10){
            data=l1->val+Addflag;
            Addflag=0;
            l1=l1->next;
            InsertNode(HeadNode,data);
        }else if(l1->val+Addflag>=10){
            data=0;
            Addflag=1;
            l1=l1->next;
           InsertNode(HeadNode,data);
        }
    }else if(l1==NULL&&l2!=NULL){
        if(l2->val+Addflag<10){
            data=l2->val+Addflag;
            Addflag=0;
            l2=l2->next;
            InsertNode(HeadNode,data);
        }else if(l2->val+Addflag>=10){
            data=0;
            Addflag=1;
            l2=l2->next;
            InsertNode(HeadNode,data);
        }
    }else if(l1==NULL&&l2==NULL){
        if(Addflag){
            InsertNode(HeadNode,1);
        } break;    
    }
}
    HeadNode=HeadNode->next;
    return HeadNode;  
}

5.反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

解法参考：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pre=NULL;
        ListNode* pos=head;
            while(pos!=NULL)
            {
            ListNode* temp=pos->next;
            pos->next = pre;
            pre = pos;
            pos = temp;  
            }
        return pre;       //最后循环完毕时 pos指向空 pre为最后一个结点
        }
};
//方法2：
    // {
    //     ListNode* pre=NULL;
    //     ListNode* pos=head;
    //     while(pos!=NULL)
    //     {
    //         ListNode* temp = pos->next;
    //         pos->next=pre;
    //         pre=pos;
    //         pos=temp;
    //     }
        
    //     return pre;
    // }

    //     if(head == NULL)
    //     {
    //         return head;        
    //     }else if (head->next==NULL)
    //     {
    //         return head;
    //     }
    //     ListNode* pre=head;
    //     ListNode* pos=head->next;
    //     if(pos->next==NULL)   //若只有两个结点 则直接换个顺序返回
    //     {
    //         pre->next=NULL;
    //         pos->next=pre;
    //         return pos;
    //     }
    //         while(pos!=NULL)
    //     {
    //         ListNode* temp=pos->next;
    //         pos->next = pre;
    //         pre = pos;
    //         pos = temp;  
    //     }
    //     return pre;       //最后循环完毕时 pos指向空 pre为最后一个结点
    // }

#23届找工作求助阵地##笔试##笔试题##编程##链表题#

嵌入式软件校招笔面试题汇总文章被收录于专栏

该专栏是我整理的一些嵌入式软件笔面试常见的题目，在有一定计算机基础上，再过一遍该专栏的内容，对应届生校招来说基本上笔面试就没什么问题了！有任何疑问可随时与我联系，一起交流一起进步。