🌺234. 回文链表
🍁题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
🍁基础框架
C++ 版本给出的基础框架代码如下：
/** * 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: bool isPalindrome(ListNode* head) { } };
🍁详细思路
🍀思路一【双指针】
将链表中所有元素存储到容器中
使用双指针，判断是否为回文链表
💬 代码演示
/** * 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: bool isPalindrome(ListNode* head) { vector<int> vals; while (head != nullptr) { vals.push_back(head->val); head = head->next; } for (int i = 0, j = vals.size() - 1; i < j; ++i, --j) { if (vals[i] != vals[j]) { return false; } } return true; } };
🍀思路二【快慢指针】
为了避免O(n)的空间复杂度，我们可以改变输入，也就是改变题目所给的链表。
我们将链表的后半部分反转，再与前半部分作比较，判断是否为回文链表
使用快慢指针，快指针一次走两步，满指针一次走一步。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
反转后半部分的链表。
判断是否回文
💬 代码演示
/** * 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: bool isPalindrome(ListNode* head) { if (head == nullptr) return true; ListNode* halfNode = halfList(head); ListNode* endNode = reverseList(halfNode->next); ListNode* p1 = head; ListNode* p2 = endNode; while (p2 != nullptr) { if (p1->val != p2->val) { return false; } p1 = p1->next; p2 = p2->next; } return true; } ListNode* halfList(ListNode* head) //快慢指针确立中间结点 { ListNode* fast = head; ListNode* slow = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* reverseList(ListNode* head) //反转链表 { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } };
🌺1669. 合并两个链表
🍁题目描述
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。
提示：
3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104
🍁基础框架
C++ 版本给出的基础框架代码如下：
/** * 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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { } };
🍁详细思路
🍀思路一【快慢指针】
快指针向前遍历list1，到a点停下，做一个标记
快指针继续遍历list1，遍历到b+1点停止，插入list2
连接list1的后半部分
💬 代码演示
/** * 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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { int fast=0; ListNode*pre=new ListNode(0); ListNode*prehead=pre; pre->next=list1; ListNode*secondhead=list1; while(fast!=a) { fast++; pre=pre->next; } ListNode*first_tail=pre; while(fast!=b+1) { fast++; pre=pre->next; } secondhead=pre->next; ListNode*curr=list2; while(curr->next) { curr=curr->next; } first_tail->next=list2; curr->next=secondhead; return prehead->next; } };
