当前位置：首页 > news >正文

探秘链表：十大经典题目全解析

news 2024/11/15 17:06:00

💯前言

💯常见链表题目类型

⭐反转链表

⭐合并两个有序链表

⭐检测链表中是否存在环

⭐找到链表的中间节点

⭐删除链表中的节点

⭐判断两个链表是否相交

⭐找到链表中环的入口节点

⭐复制带随机指针的链表

💯解题技巧与注意事项

⭐画图辅助理解

⭐注意边界情况

⭐代码实现的简洁性与效率

💯总结

💯前言

在计算机科学与技术的世界里，链表是一种重要的数据结构。它在许多算法和程序中都有着广泛的应用。本文将深入分析一些常见的链表题目，帮助你更好地理解和掌握链表的概念与操作。

链表的基本概念👉【链表】

💯常见链表题目类型

⭐反转链表

题目链接👉【力扣】

题目描述：给定一个单链表，将其反转，并返回反转后的链表头节点。
示例：输入链表 1->2->3->4->5，输出 5->4->3->2->1。
解题思路：
- 迭代法：使用三个指针 prev（指向当前节点的前一个节点）、cur（指向当前节点）和 next（指向当前节点的下一个节点）。遍历链表，每次将 cur 的 next 指针指向 prev，然后更新 prev 为 cur，cur 为 next，直到 cur 为 null，此时 prev 指向的就是反转后的链表头节点。
- 递归法：先递归反转链表的后续部分，然后将当前节点的 next 指针指向 null，再将当前节点设为反转后链表的头节点。
复杂度分析：时间复杂度为O(n) ，其中 n 是链表的长度，因为需要遍历整个链表。空间复杂度为 O(1)（迭代法）或 O(n)（递归法，取决于递归调用栈的深度）

1.迭代法

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;//指向已经反转好的链表部分的最后一个节点struct ListNode* curr = head;struct ListNode* next = NULL;while (curr!= NULL) {next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}

💡代码解析：

1. 初始化三个指针：

   ●   prev 初始化为 NULL，用于指向已经反转好的链表部分的最后一个节点，初始时反转后的链表为空，所以 prev 为 NULL。

   ●   curr 初始化为传入的链表头指针 head，表示当前正在处理的节点。

   ●   next 初始化为 NULL ，用于暂存当前节点的下一个节点，以便在修改当前节点的指针后能够继续遍历链表。

2. 迭代反转链表：

   ●   进入循环，只要 curr 不为NULL，就继续执行反转操作。

   ●   首先，将 next 指针指向当前节点 curr 的下一个节点，保存当前节点的下一个位置。

   ●   然后，将当前节点 curr 的 next 指针指向前一个节点 prev ，实现反转。

   ●   接着，将 prev 指针更新为当前节点 curr ，表示 prev 现在指向已经反转好的链表部分的最后一个节点。

   ●   最后，将 curr 指针更新为 next ，继续处理下一个节点。

3. 返回反转后的链表头指针：

● 当循环结束时，curr 为 NULL，此时 prev指向反转后的链表的头节点，返回 prev 。

2.递归法

struct ListNode* reverseListRecursive(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head;}struct ListNode* reversedList = reverseListRecursive(head->next);head->next->next = head;head->next = NULL;return reversedList;
}

💡代码解析：

1. 递归终止条件判断：

● 首先检查链表是否为空（head == NULL）或者链表只有一个节点（head->next == NULL）。在这两种情况下，无需进行反转操作，直接返回当前链表的头指针 head。

2. 递归调用：

● 如果链表不止一个节点，那么递归地调用 reverseListRecursive(head->next)，对链表中除了当前节点之外的部分进行反转。假设这部分已经被正确反转，返回的结果是反转后的链表头指针，赋值给 reversedList。

3. 反转当前节点与下一个节点的关系：

● 将当前节点 head 的下一个节点（此时已经是反转后的链表的一部分）的 next 指针指向当前节点 head，即 head->next->next = head。这样就实现了将当前节点插入到反转后的链表的开头。

● 然后将当前节点 head 的 next 指针置为NULL，以确保反转后的链表的最后一个节点的next 为 NULL。

4. 返回反转后的链表头指针：

● 最后返回 reversedList，它是整个反转后的链表的头指针。

⭐合并两个有序链表

题目链接👉【力扣】

题目描述：将两个有序的单链表合并成一个有序的单链表。
示例：链表 1->3->5 和链表 2->4->6，合并后为 1->2->3->4->5->6。
解题思路：创建一个新的链表头节点 dummy，设置两个指针 p1 和 p2 分别指向两个输入链表的头节点。比较 p1 和 p2 所指节点的值，将较小值的节点添加到新链表中，并移动相应的指针。重复此过程，直到 p1 或 p2 为 null，然后将剩余的链表部分添加到新链表的末尾。
复杂度分析：时间复杂度为 O(n+m)，其中 n 和 m 分别是两个输入链表的长度。空间复杂度为 O(1)，因为只使用了常数个额外的指针。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curr = dummy;while (l1 && l2) {if (l1->val < l2->val) {curr->next = l1;l1 = l1->next;} else {curr->next = l2;l2 = l2->next;}curr = curr->next;}curr->next = l1? l1 : l2;return dummy->next;
}

💡代码解析：

1. 边界情况处理：

● 首先检查两个输入链表是否为空。如果 l1 为空，直接返回 l2 ；如果l2 为空，直接返回 l1 。

2. 创建哑节点和当前指针：

● 创建一个哑节点 dummy，用于简化合并过程的指针操作。设置一个指针 curr 指向这个哑节点。

3. 比较并合并节点：

   ●   当两个链表都不为空时，进入循环。

   ●   比较两个链表当前节点的值，如果 l1 的当前节点值小于l2 的当前节点值，将curr 的下一个指针指向 l1 的当前节点，然后将 l1 指针后移到下一个节点。

   ●   否则，将 curr 的下一个指针指向l2 的当前节点，然后将 l2 指针后移到下一个节点。

   ●   最后将curr 指针后移到下一个节点。

4. 处理剩余链表：

● 当循环结束后，可能有一个链表还有剩余节点。将curr 的下一个指针指向非空的链表（ l1 或 l2 ）。

5. 返回合并后的链表头指针：

● 返回dummy的下一个指针，即为合并后的链表的头指针。

⭐检测链表中是否存在环

题目链接👉【力扣】

题目描述：判断给定的链表中是否存在环。
示例：链表 1->2->3->4->5->2（其中 5 的 next 指向 2，形成环），返回 true；链表 1->2->3->4->5->null，返回 false。
解题思路1：使用快慢指针法。定义两个指针 slow 和 fast，初始时都指向链表的头节点。slow 每次移动一步，fast 每次移动两步。如果链表中存在环，那么 fast 一定会在某个时刻追上 slow（即 fast 和 slow 指向同一个节点）；如果 fast 到达链表末尾（fast 或 fast->next 为 null），则说明链表中不存在环。
复杂度分析：时间复杂度为O(n) ，其中 n 是链表中节点的数量。在最坏情况下，需要遍历整个链表才能确定是否存在环。空间复杂度为 O(1)，只使用了两个额外的指针。

bool hasCycle(struct ListNode *head){struct ListNode *slow = head;struct ListNode *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {return true;}}return false;
}

💡代码解析：

1. 使用快慢指针：

● 初始化两个指针 slow 和 fast，都指向链表的头节点 head。

● slow 指针每次移动一步，fast 指针每次移动两步。

2. 遍历链表：

● 进入循环，条件是fast指针和 fast->next 指针都不为 NULL。这是为了确保在移动fast 指针时不会出现空指针访问错误。

● 在每次循环中，slow 指针移动一步，fast 指针移动两步。

3. 检测是否有环：

● 如果在遍历过程中，slow 和 fast 指针相遇，说明链表中有环，返回 true。

● 如果循环结束时，fast 指针或者 fast->next 指针为NULL，说明链表中没有环，返回 false 。

⭐找到链表的中间节点

题目链接👉【力扣】

题目描述：给定一个非空链表，找到其中的中间节点。如果有两个中间节点，则返回第二个中间节点。
示例：对于链表 1->2->3->4->5，中间节点是 3；对于链表 1->2->3->4->5->6，中间节点是 4。
解题思路：使用快慢指针。slow 指针每次移动一步，fast 指针每次移动两步。当 fast 到达链表末尾时，slow 正好位于中间位置。
复杂度分析：时间复杂度为O(n) ，其中 n 是链表的长度。fast 指针遍历了链表的前半部分，slow 指针遍历了链表的后半部分，总体时间复杂度为线性。空间复杂度为O(1) ，只使用了两个额外的指针。

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

💡代码解析：

1. 使用快慢指针：

● 初始化两个指针slow 和 fast ，都指向链表的头节点 head。

● slow 指针每次移动一步，fast 指针每次移动两步。

2. 遍历链表：

● 进入循环，条件是fast 指针不为 NULL且 fast->next 指针也不为 NULL。这是为了确保在移动 fast 指针时不会出现空指针访问错误。

● 在每次循环中，slow 指针移动一步，fast 指针移动两步。

3. 返回中间节点：

● 当 fast 指针到达链表末尾或者超出末尾时，slow 指针正好位于链表的中间位置。返回 slow 指针所指向的节点，即为链表的中间节点。

⭐删除链表中的节点

题目链接👉【力扣】

题目描述：给定一个链表的头节点 head 和一个整数 val，删除链表中所有值等于 val 的节点，并返回新的链表头节点。
示例：输入链表 1->2->6->3->4->5->6，val = 6，输出 1->2->3->4->5。
解题思路：遍历链表，使用一个指针 prev 记录当前节点的前一个节点，当遇到值等于 val 的节点时，将 prev 的 next 指针指向当前节点的下一个节点，从而跳过该节点。特殊情况包括：如果头节点的值等于 val，则需要更新头节点；如果整个链表的值都等于 val，则最终链表为空。
复杂度分析：时间复杂度为，其中是链表的长度，需要遍历整个链表来查找和删除节点。空间复杂度为，只使用了常数个额外的指针。

struct ListNode* deleteNode(struct ListNode* head, int val){struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));dummy->next = head;struct ListNode* prev = dummy;struct ListNode* curr = head;while (curr) {if (curr->val == val) {prev->next = curr->next;free(curr);curr = prev->next;} else {prev = curr;curr = curr->next;}}return dummy->next;
}

💡代码解析：

1. 创建哑节点：

● 创建一个哑节点 dummy，将其 next 指针指向输入链表的头节点 head。这样做是为了处理删除头节点的情况时更加方便。

2. 遍历链表：

● 使用两个指针 prev 和 curr 遍历链表。prev 始终指向curr 的前一个节点。

● 当 curr 不为 NULL 时，进入循环。

3. 找到要删除的节点：

● 如果当前节点curr 的值等于要删除的值 val，则将prev 的 next 指针指向curr 的下一个节点，即跳过当前要删除的节点。然后释放curr 节点的内存。最后跳出循环。

4. 返回新的头节点：

● 循环结束后，返回 dummy->next，即删除节点后的链表的头节点。如果删除的是头节点，那么新的头节点就是dummy->next；如果删除的不是头节点，dummy->next也指向正确的新头节点。

⭐判断两个链表是否相交

题目链接👉【力扣】

题目描述：判断两个链表是否相交，即它们是否有共同的节点。
解题思路：可以通过比较两个链表的尾节点是否相同来判断。如果尾节点相同，则说明两个链表相交，此时可以从相交点开始，同时遍历两个链表，直到节点相同为止，该节点即为相交点。如果尾节点不同，则两个链表不相交。
复杂度分析：时间复杂度为O(n+m) ，其中 n 和 m 分别是两个链表的长度，需要遍历两个链表。空间复杂度为O(1) ，只使用了常数个额外的指针。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (headA == NULL || headB == NULL) {return NULL;}struct ListNode *pA = headA, *pB = headB;while (pA != pB) {pA = pA == NULL ? headB : pA->next;pB = pB == NULL ? headA : pB->next;}return pA;
}

💡代码解析：

以下是对这段代码的逐步解释：

首先，函数 getIntersectionNode 用于找出两个链表 headA 和 headB 的相交节点。

在函数开头，检查如果headA 或者headB 为 NULL，直接返回 NULL，这是因为如果其中一个链表为空，就不可能有相交节点。

然后，定义两个指针 pA 和 pB，分别初始化为headA 和headB 。

接下来，进入一个 while 循环，只要 pA 和 pB 不相等，就一直循环。

在循环内部，如果 pA 到达了链表 A 的末尾（即 pA 为 NULL），就将 pA 指向链表 B 的头节点 headB ，以便从链表 B 继续比较。

同样，如果 pB 到达了链表 B 的末尾（即 pB 为 NULL），就将 pB 指向链表 A 的头节点headA ，以便从链表 A 继续比较。

这样做的目的是通过让两个指针在两个链表上遍历，最终如果两个链表有相交节点，那么这两个指针一定会在相交节点处相遇。

当 pA 和 pB 相等时，就找到了相交节点，此时返回 pA 或者 pB 都可以，因为它们指向的是同一个节点。

综上所述，这个函数通过巧妙地让两个指针在两个链表上交替遍历，来找出相交节点

⭐找到链表中环的入口节点

题目链接👉【力扣】

题目描述：在一个给定的链表中，存在一个环，找到环的入口节点1。
解题思路1：使用快慢指针找到环中的相遇点，然后定义一个指针从链表头开始，另一个指针从相遇点开始，同时以相同速度移动，它们相遇的地方就是环的入口节点。
- 设链表头到环入口的距离为 a，环入口到快慢指针相遇点的距离为 b，相遇点到环入口的距离为 c 。
- 当快慢指针相遇时，快指针走过的路程是慢指针的两倍，即2(a+b) = a+b+n(b+c) ，其中 n 为快指针在环中走的圈数。
- 化简可得，这意味着从链表头和相遇点同时出发，第一次相遇的节点就是环的入口节点。
复杂度分析：时间复杂度为O(n) ，其中 n 是链表的长度。空间复杂度为O(1) ，只使用了常数个额外的指针。

// 找到链表中环的入口节点
struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;// 先找到快慢指针相遇的位置while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {break;}}// 如果没有环，返回 NULLif (!fast ||!fast->next) {return NULL;}// 重置快指针到链表头fast = head;// 快慢指针再次移动，相遇点即为环的入口节点while (slow!= fast) {slow = slow->next;fast = fast->next;}return slow;
}

💡代码解析：
1. 初始化快慢指针并寻找相遇点：

struct ListNode* slow = head;
struct ListNode* fast = head;// 先找到快慢指针相遇的位置
while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {break;}
}

初始化两个指针 slow 和 fast 都指向链表的头节点head。
进入循环，只要fast 和fast->next不为NULL，循环就会继续。这是为了确保在移动fast 指针时不会出现空指针访问错误。
slow 指针每次移动一步，fast 指针每次移动两步。
如果在移动过程中slow和fast 相遇了，说明链表中存在环，跳出循环。

2. 判断是否有环并返回结果：

// 如果没有环，返回 NULL
if (!fast ||!fast->next) {return NULL;
}

如果循环结束后fast 或者fast->next为NULL，说明链表中没有环，直接返回NULL。

3. 找到环的入口节点：

fast = head;// 快慢指针再次移动，相遇点即为环的入口节点
while (slow!= fast) {slow = slow->next;fast = fast->next;
}return slow;

当确定链表中有环后，将fast 指针重新指向链表的头节点。
然后让slow 和fast 指针都每次移动一步。
当slow 和fast 再次相遇时，此时的节点就是环的入口节点，返回这个节点。

⭐复制带随机指针的链表

代码链接👉【力扣】

题目描述：对于一个带有随机指针的链表，复制出一个完全相同的链表，新链表中的每个节点都包含一个随机指针，指向原链表中的任意一个节点或者 null。
解题思路：可以使用哈希表来存储原链表节点和新链表节点的对应关系。首先，遍历原链表，创建新链表的节点，并将原链表节点和新链表节点放入哈希表中。然后，再次遍历原链表，根据哈希表中存储的对应关系，设置新链表节点的 next 指针和 random 指针。
复杂度分析：时间复杂度为 O(n)，其中 n 是原链表的长度，需要遍历两次链表。空间复杂度为，O(n) 用于存储哈希表。

// 复制链表
Node* copyRandomList(Node* head) {if (head == NULL) return NULL;// 第一步：在原链表的每个节点后插入复制的节点Node* curr = head;while (curr!= NULL) {Node* newNode = createNode(curr->val);newNode->next = curr->next;curr->next = newNode;curr = newNode->next;}// 第二步：设置复制节点的 random 指针curr = head;while (curr!= NULL) {if (curr->random!= NULL) {curr->next->random = curr->random->next;}curr = curr->next->next;}// 第三步：分离原链表和复制后的链表Node* newHead = head->next;curr = head;Node* temp;while (curr!= NULL && curr->next!= NULL) {temp = curr->next;curr->next = temp->next;curr = temp;}return newHead;
}

💡代码解析：

1. 处理空链表：