逐日一题——三道链表简单题：回文，环形归并有序

链表是数据布局中的重要构成部分，也是面试中经常考察的内容。本文将详细先容三道经典的链表问题：回文链表、环形链表和归并两个有序链表。我们将从问题描述、解题思路、代码实现以及复杂度分析等方面举行详细解说。
1. 回文链表

1.1 问题描述

给定一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：

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

1.2 解题思路

判断回文链表的关键在于如何高效地比力链表的前半部分和后半部分。常见的方法是使用快慢指针找到链表的中点，然后反转后半部分链表，最后举行比力。这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。
详细步骤如下：

• 找到链表中点：使用快慢指针，快指针每次走两步，慢指针每次走一步。当快指针到达链表末尾时，慢指针恰好位于链表中点。
  
• 反转后半部分链表：从链表中点开始，反转后半部分链表。
  
• 比力前后两部分：从链表头部和反转后的后半部分头部开始，逐节点比力。
  
• 恢复链表：比力完成后，将链表恢复原状（可选）。
  
• 返回结果：如果所有节点都匹配，则返回 true，否则返回 false。
  

1.3 代码实现

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
9. // 反转链表函数
10. struct ListNode* reverse(struct ListNode* head) {
11.     if (head == NULL || head->next == NULL) {
12.         return head;
13.     }
14.     struct ListNode* pre = NULL;
15.     struct ListNode* next = NULL;
16.     while (head) {
17.         next = head->next;
18.         head->next = pre;
19.         pre = head;
20.         head = next;
21.     }
22.     return pre;
23. }
25. // 判断回文链表
26. bool isPalindrome(struct ListNode* head) {
27.     if (head == NULL || head->next == NULL) {
28.         return true;
29.     }
31.     // 使用快慢指针找到链表中点
32.     struct ListNode* slow = head;
33.     struct ListNode* fast = head;
34.     while (fast->next != NULL && fast->next->next != NULL) {
35.         slow = slow->next;
36.         fast = fast->next->next;
37.     }
39.     // 反转后半部分链表
40.     slow->next = reverse(slow->next);
42.     // 比较前后两部分
43.     slow = slow->next;
44.     while (slow != NULL) {
45.         if (head->val != slow->val) {
46.             return false;
47.         }
48.         head = head->next;
49.         slow = slow->next;
50.     }
52.     return true;
53. }

复制代码

1.4 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历链表两次。
  
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。
  

---

2. 环形链表

2.1 问题描述

给定一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。返回 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^4]
  
• -10^5 <= Node.val <= 10^5
  

2.2 解题思路

判断链表中是否存在环的经典方法是使用快慢指针。快指针每次走两步，慢指针每次走一步。如果链表中存在环，快指针最终会追上慢指针；如果链表中没有环，快指针会先到达链表末尾。
2.3 代码实现

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
9. bool hasCycle(struct ListNode* head) {
10.     if (head == NULL || head->next == NULL) {
11.         return false;
12.     }
14.     struct ListNode* slow = head;
15.     struct ListNode* fast = head;
17.     while (fast != NULL && fast->next != NULL) {
18.         slow = slow->next;
19.         fast = fast->next->next;
21.         if (slow == fast) {
22.             return true; // 发现环
23.         }
24.     }
26.     return false; // 未发现环
27. }

复制代码

2.4 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。在最坏情况下，快指针会遍历整个链表。
  
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。
  

---

3. 归并两个有序链表

3.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 均按非递减顺序排列
  

3.2 解题思路

归并两个有序链表的关键在于如何高效地将两个链表的节点按顺序拼接。我们可以使用一个假造头节点（dummy node）来简化操作，并通过迭代的方式逐节点比力和拼接。
3.3 代码实现

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
9. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
10.     struct ListNode dummy; // 虚拟头节点
11.     dummy.next = NULL;
12.     struct ListNode* tail = &dummy; // 指向结果链表的尾部
14.     while (list1 != NULL && list2 != NULL) {
15.         if (list1->val < list2->val) {
16.             tail->next = list1;
17.             list1 = list1->next;
18.         } else {
19.             tail->next = list2;
20.             list2 = list2->next;
21.         }
22.         tail = tail->next;
23.     }
25.     // 拼接剩余的链表
26.     if (list1 != NULL) {
27.         tail->next = list1;
28.     } else {
29.         tail->next = list2;
30.     }
32.     return dummy.next; // 返回合并后的链表头节点
33. }

复制代码

3.4 复杂度分析

• 时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度。我们需要逐节点比力并拼接。
  
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。
  

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。