# 链表问题（二）-LeetCode 147、876、234、817、92（链表的中点，快慢指针）

1

【LeetCode #147】对链表进行插入排序

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* dummy = new ListNode(), *pre = nullptr;
continue;
}
pre = dummy;
pre = pre->next;
}
cur->next = pre->next;
pre->next = cur;
}
return dummy->next;
}
};
```

【LeetCode #876】链表的中间结点

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
```

【LeetCode #234】回文链表

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
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;
}
return false;
}
pre = pre->next;
}
return true;
}
};
```

【LeetCode #817】链表组件

```/**
* 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
if(it != s.end()){   // 找到了
flag = true;
}else{               // 没找到，前面的作为一个组件
if(flag){ res++; }
flag = false;
}
}
if(flag) res++;
return res;
}
};
```

【LeetCode #92】反转链表 II

```/**
* 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();
ListNode* pre = dummy;
for(int i = ; i < m; i++){
pre = pre->next;
}
for(int i = m; i < n; i++){
tmp->next = pre->next;
pre->next = tmp;
}
return dummy->next;
}
};
```

0 条评论

• ### 链表问题-LeetCode 206、234、160（反转，回文，公共结点）

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

• ### 每日算法题：Day 27（机器学习）

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符...

• ### 每日算法题：Day 18（概率统计）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的...

• ### Leetcode 24. Swap Nodes in Pairs

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### Leetcode 142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cyc...

• ### 剑指Offer LeetCode 面试题18. 删除链表的节点

输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该...

• ### Leetcode 82 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leavi...

• ### LintCode-452.删除链表中的元素

给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。