链表问题（二）-LeetCode 147、876、234、817、92（链表的中点，快慢指针）
链表问题（二）-LeetCode 147、876、234、817、92（链表的中点，快慢指针）
1
编程题
【LeetCode #147】对链表进行插入排序
对链表进行插入排序。
示例 1： 输入: 4->2->1->3 输出: 1->2->3->4
解题思路：
首先判断两个相邻节点的大小，如果head->val > head->next->val，则需要将head->next->val插入到从dummy节点开始遍历第一个大于head->next->val节点的前面！好好理解这句话！在进行插入的时候，首先使用cur指针标记head->next节点，并改变head->next的指向。从而将待插入节点分离！接着就是普通的插入操作了！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* dummy = new ListNode(), *pre = nullptr;
dummy->next = head;
while(head->next != nullptr){
if(head->val <= head->next->val){ // 无需进行插入操作
head = head->next;
continue;
}
pre = dummy;
while(pre->next->val < head->next->val){
pre = pre->next;
}
ListNode* cur = head->next;
head->next = cur->next;
cur->next = pre->next;
pre->next = cur;
}
return dummy->next;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/insertion-sort-list/
【LeetCode #876】链表的中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。
示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。(测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
解题思路：快慢指针，注意与下一题中的回文链表的中间结点进行区别！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* slow = head, *fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
【LeetCode #234】回文链表
请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false
解题思路：
找到中点（奇数时不是真正的中点，注意与上题区别），然后反转后面的链表，再进行节点值得比较即可！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head, *fast = head, *pre = nullptr;
while(fast != nullptr){
slow = slow->next;
fast = fast->next ? fast->next->next : nullptr;
} // 这里的中点偶数时为第二个节点，奇数时为中点的下一个节点！
while(slow != nullptr){
ListNode* next = slow->next;
slow->next = pre;
pre = slow;
slow = next;
}
while(pre && head){
if(pre->val != head->val){
return false;
}
pre = pre->next;
head = head->next;
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
【LeetCode #817】链表组件
给定一个链表（链表结点包含一个整型值）的头结点 head。 同时给定列表 G，该列表是上述链表中整型值的一个子集。 返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
示例 1： 输入: head: 0->1->2->3 G = [0, 1, 3] 输出: 2 解释: 链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
解题思路：
一开始题目没有看太懂，可能语文不太好！他的意思就是，如果连续相邻的链表节点值都在G这个数组中，那么这为一个组件，如果不在，则忽略！最终答案是G中有多少个组件。 比如0->1->3->2, 而G = [1,3,0] 则答案为 1。 我们查询可以在set中进行，设置布尔变量flag的作用是：用true标记这是一个组件，而false表示组件断开了，此时res++, 但有可能我们遍历的节点一直都不在G中。因此res++需要一个条件限制，即flag = true.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
set<int> s(G.begin(), G.end());
int res = ;
bool flag = false; // 找到标记为true
while(head != nullptr){
auto it = s.find(head->val);
if(it != s.end()){ // 找到了
flag = true;
}else{ // 没找到，前面的作为一个组件
if(flag){ res++; }
flag = false;
}
head = head->next;
}
if(flag) res++;
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-components
【LeetCode #92】反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* pre = dummy;
for(int i = ; i < m; i++){
pre = pre->next;
}
head = pre->next;
for(int i = m; i < n; i++){
ListNode* tmp = head->next;
head->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
}
return dummy->next;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list-i