链表面试题

💓作者简介👏：在校大二迷茫大学生

💖个人主页🎉：小李很执着

💗系列专栏：Leetcode经典题

每日分享：其实要过那条马路并不难，就看谁在对面等你❣️❣️❣️

💝1.876. 链表的中间结点

❣️1.题目

❣️2.解答：快慢指针法

💝2.21. 合并两个有序链表

❣️1.题目

❣️2.解答：双指针遍历两个链表

💝3.OR36 链表的回文结构

❣️1.题目

❣️2.解答：快慢指针和链表反转

💝4.138.随机链表的复制

❣️ 1.题目：

❣️2.解答

💝1.876. 链表的中间结点

876. 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/

❣️1.题目

给你单链表的头结点 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

❣️2.解答：快慢指针法

算法思路：

使用快慢指针，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针正好到达中间位置。

具体实现：

首先定义两个指针 slow 和 fast 都指向链表头节点 head。然后使用 while 循环遍历链表，当快指针 fast 到达链表的末尾或者为空时，遍历结束。在循环过程中，每次快指针移动两步，慢指针移动一步。最终返回慢指针 slow，即为链表的中间节点。

遍历两遍：

第一遍：求出链表的长度

第二遍：长度/2

struct ListNode*middleNode(struct ListNode* head)
{
struct ListNode*slow =head,*fast =head;
while(fast &&fast->next)
{
slow =slow->next;
fast =fast->next->next;
}
return slow;
}

💝2.21. 合并两个有序链表

21. 合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/

❣️1.题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

❣️2.解答：双指针遍历两个链表

通过使用双指针遍历两个链表，将较小的节点依次加入新链表中。具体实现步骤如下：

首先判断两个链表中是否有空链表，若有则直接返回不为空的链表。

定义一个新链表的头指针head和尾指针tail，初始值均为NULL。

使用while循环遍历list1和list2，比较当前节点的值大小，将较小的节点添加到新链表中。

当一个链表遍历完后，将另一个链表中剩余的节点全部添加到新链表的尾部。

返回新链表的头指针head。

需要注意的是，在添加节点到新链表时需要更新尾指针tail。另外，最后返回的是新链表的头指针head，而不是尾指针tail。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
if(list1==NULL)
return list2;

if(list2==NULL)
return list1;
struct ListNode* tail = NULL,*head = NULL;
while(list1 && list2)
{
if(list1->val < list2->val)
{
if(tail == NULL)
{
head = tail = list1;
}
else
{
tail->next = list1;
tail = tail->next;
}
list1 = list1->next;
}
else
{
if(tail == NULL)
{
head = tail = list2;
}
else
{
tail->next = list2;
tail = tail->next;
}
list2 = list2->next;
}
}
if(list1)
tail->next = list1;
if(list2)tail->next = list2;
return head;  
}

💝3.OR36 链表的回文结构

❣️1.题目

描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：
1->2->2->1
返回：true

❣️2.解答：快慢指针和链表反转

具体思路如下：

使用快慢指针找到链表的中间节点，如果链表长度是奇数，则中间节点是正中间的那个节点，如果长度是偶数，则中间节点是偏右的那个节点。

将链表的后半部分进行反转操作。

分别从链表头和反转后的链表头开始向中间遍历，比较每个节点的值是否相等，如果有不相等的则说明不是回文链表。

如果整个链表都遍历完了并且每个节点的值都相等，则说明是回文链表。

代码中定义了三个函数：

reverseList：链表反转函数，输入一个链表头节点，返回反转后的链表头节点。

middleNode：快慢指针找中间节点函数，输入链表头节点，返回中间节点。

chkPalindrome：判断是否为回文链表的函数，输入链表头节点，返回是否为回文链表。

class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur) {
        struct ListNode* next = cur->next;// 头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
bool chkPalindrome(ListNode* head) {
    struct ListNode* mid = middleNode(head);
    struct ListNode* rhead = reverseList(mid);
    while (head && rhead) {
        if (head->val != rhead->val)
            return false;
        head = head->next;
        rhead = rhead->next;
    }
    return true;
}

    
};

💝4.138.随机链表的复制

138. 随机链表的复制https://leetcode.cn/problems/copy-list-with-random-pointer/

❣️ 1.题目：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 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]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

❣️2.解答

在原链表中每个节点的后面插入一个新的节点，新节点的值等于原节点的值，新节点的 next 指针等于原节点的 next 指针。

复制随机指针：对于原链表中的每个节点 cur，将其新节点 copy 的随机指针指向原节点 cur 的随机指针指向节点的下一个节点。

分离新旧链表：将新链表的头结点和尾结点初始化为 NULL，然后遍历原链表中的每个节点 cur，将 cur 的新节点 copy 从原链表中分离出来，加入到新链表的尾部。最后，将原链表和新链表断开连接，并将新链表的头结点作为结果返回。

该方法的时间复杂度为 O(n)，其中 n 是链表中节点的个数。空间复杂度为 O(n)，需要额外的空间存储每个节点的复制品。

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    while(cur)
    {
      struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
      copy->val = cur->val;
      copy->next = cur->next;
      cur->next = copy;
//cur = copy->next;
      cur = cur->next->next;
    }
cur = head;
while(cur)
{
struct Node* copy = cur->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
//cur = copy->next;
cur = cur->next->next;
}
struct Node* newhead = NULL,*tail = NULL;
cur = head;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
if(tail == NULL)
{
newhead = tail = copy;
}
else
{
tail->next = copy;
tail = tail->next;
}
cur->next = next;
cur = next;
}
return newhead;
	
}