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