05-26 12:18 联发科技_智慧产品软件开发部_Android BSP

关注

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

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

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

1.环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [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) {}
 * };
 */

//简单的方法使用哈希表，但是内存占了n，进阶可以用快慢指针，当指针相遇时，慢指针移到头部，一起继续走，注意快指针此时也改成一步，当再次相遇时就是环的入口。
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if(head == NULL || head->next == NULL )
        {
            return NULL;
        }

        ListNode* fast= head;
        ListNode* slow= head;    
        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)       //找到了开始做处理
            {
                slow = head;
                while(slow != fast)
                {
                    fast = fast->next;
                    slow = slow->next;
                    //result++;                    
                }
                return slow;
            }
        }
        return NULL;
    }
};

2.链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

解法参考：

/*第一印象就是双指针，快慢指针，当快的到末尾(或)时，慢的就是中间结点*/
/**
 * 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* middleNode(ListNode* head) 
    {
        ListNode* fast = head;     
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL)   //短路求值注意判断条件的顺序
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

3.复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

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

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

解法参考：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
/*
这道题难点就在于多了个随机指针，如果没有随机指针，那么直接搞一个前驱结点pre然后开始遍历就可以了，但多了个随机结点，没办法找到一个像前驱节点这样跟本节点这样挂钩明确的可遍历的，所以没办法直接遍历一遍。
几种方法：
一：借助哈希表，表内容为<Node*,Node*>型，里面为新结点跟旧结点的对应，然后直接遍历一遍把旧结点复制一遍(单纯是赋了val值)，然后再通过遍历哈希表，把新结点的next和random给补充完整

二：复制链表，新结点直接连在对应旧节点的后面，1-1*-2-2*-3-3*....这样新结点的next值已经确定好了，接下来就去遍历旧结点(旧结点的遍历是要.next.next)，然后确定新节点的random值，因为有新节点.random = 旧节点.random.next，所以遍历完成后就整个复制好了，接下来就是把链表拆分开就可以，拆分也很简单，让旧结点.next = 旧结点.next.next 新节点也同样，遍历就完事，最后返回那个头。用这种方法就空间复杂度只有1
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        // 5. 返回新链表的头节点
        return map[head];
    }
};

//这里用下第二种方法，效率高点
/*class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
      if(head == NULL) return head;
      Node* pos = head;          
      //Node* posnext = head->next;  
      while(pos != NULL)   //遍历一次链表就把val和next搞定
      {
          Node* npos = new Node(pos->val);
          npos->next = pos->next;  
          pos->next = npos;
          pos = npos->next;
          //if(posnext != NULL)
          //posnext = posnext->next;  
      }  
       pos = head; 
      while(pos != NULL)   //遍历第二次链表就把random搞定
      {
          //注意在random这里要判断一下这个random是不是指向null，不然null的next没有意义
          if(pos->random == NULL) continue;
          pos->next->random = pos->random->next;
          pos = pos->next->next;  
      }  
      pos = head->next;
      //posnext = head->next;
      Node* result = head->next;
      Node* posnext = head;
      while(pos->next != NULL)     //最后把链表拆开，返回出去  
    {
        pos->next = pos->next->next;
        pos = pos->next;

        posnext->next = posnext->next->next;
        posnext = posnext->next;
    }
        pos->next = NULL;
        return result;
    }
};
*/

4.删除排序链表中的重复元素

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

解法参考：

/**
 * 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* deleteDuplicates(ListNode* head) 
    {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *pos = head;
        while(pos->next != NULL)
        {
            if(pos->val != (pos->next->val))
            {
                pos = pos->next;    
            }else
            {
                pos->next = pos->next->next;
            //    pos = pos->next;    这一步不能写，写了导致bug  因为这样子若有多个同样重复点，直接跳到那里错过了   
            }
        }
        return head;
    }
};

5.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

解法参考：

/**
 * 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* swapPairs(ListNode* head) 
    {
        if(head == NULL || head->next == NULL) return head; 

        ListNode* next = head->next;
        head->next = swapPairs(next->next); 
        next->next = head;
        return next;
    }
};

6.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。

在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。

在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。

由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m

listB 中节点数目为 n

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点，intersectVal 为 0

如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

解法参考：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

/* 想到的几种方法
1:穷举   
2:hash表记录第一个遍历的链表
3:双指针，分别从两边的头开始，当一边到null后就换成从另一边的头开始，以此类推，当两者相等时就跳出来返回 
4:双指针，不过先分别遍历两个链表的长度，用较长的减去较短的，得到一个差值，然后长的那个指针从头部往后差值个结点开始，短的那个指针从头开始，双双向后移动，直到相遇则为第一个交点，若为null则为不相交
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {   
        ListNode* a = headA;
        ListNode* b = headB;        
        while(a != b)
        {
            a = a==NULL?headB:a->next; 
            b = b==NULL?headA:b->next; 
        }
        return a;
    }
};

7.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围[1, 10⁵] 内
0 <= Node.val <= 9

解法参考：

/**
 * 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) {}
 * };
 */

/*
1、方法一是双指针去遍历，一个从头开始 一个从尾巴，逐个比较直到相遇，过程若有不同直接跳出，注意偶数和奇数的区别，所以还要判断左边的是否跑到右边了   (即直接遍历然后把数都放到数组里面，然后在数组里面进行双指针对比)  但空间复杂度为n 
2、方法二是快慢指针结合链表反转，当快的指针到了null(偶数)或下一个就是null时(奇数)即停止，此时慢指针即为中间，(注意若快指针是null则慢指针这里就是中间，若快指针下一个才是null则慢指针要再往下走一步)，然后将慢指针为头的链表反转，快指针移动到头部，然后开始遍历比较，直到慢指针到达null   这种做法空间复杂度只为1
*/
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        if(head->next == NULL) return true;
        
        ListNode* fast = head;
        ListNode* slow = head;
        
        while(fast != NULL && fast->next != NULL )   //将快指针指到末尾  或是null或是下一个是null
        {
            fast = fast->next->next;    
            slow = slow->next;
        }
        if(fast != NULL) slow = slow->next;     //则此时链表是奇数链表
        slow = listReverse(slow);
        fast = head;
        while(slow != NULL)
        {
            if(slow->val != fast->val )
            {
                return false;
            }
            slow = slow->next;
            fast = fast->next;           
        }
        return true;
    }

 //之前返回void  直接修改  一直有bug  后面改了，直接返回反转后的头结点吧
    ListNode* listReverse(ListNode* head)     //链表反转的实现函数
    {
        if(head->next == NULL) return head;
        ListNode* result = NULL;
        ListNode* pos = head;
        ListNode* last = head->next;
        while(pos != NULL )
        {
           pos->next = result;
           result = pos;
           pos = last;
           if(last != NULL) 
           last = last->next;     
        }
        return result;
    }
};

#23届找工作求助阵地##链表题##嵌入式##笔试题目##笔面试#

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

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