链表面试题

简介: 链表面试题

❣️1.题目

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


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


示例 1:

image.png

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

输出:[3,4,5]

解释:链表只有一个中间结点,值为 3 。

示例 2:

image.png

输入: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

image.png

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. 合并两个有序链表

❣️1.题目

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


示例 1:

image.png

输入: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
  • l1l2 均按 非递减顺序 排列

❣️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. 随机链表的复制

❣️ 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:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为  null

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


示例 1:

image.png

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

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

image.png

输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

示例 3:

image.png

输入:head = [[3,null],[3,0],[3,null]]

输出:[[3,null],[3,0],[3,null]]

提示:


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

❣️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;
  
}
相关文章
|
1月前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
2月前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
|
2月前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
31 0
|
2月前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
31 0
|
2月前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
19 0
|
2月前
|
算法 测试技术
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(下)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
27 0