面试题 18. 删除链表的节点
/**
* 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* deleteNode(ListNode* head, int val) {
ListNode* dummy=new ListNode(0,head); // 虚拟头节点的值0,next指向head
for(ListNode* cur=dummy;cur->next!=nullptr;cur=cur->next){
if(cur->next->val==val){
cur->next=cur->next->next;
break;
}
}
return dummy->next;
}
};
// 时间复杂度O(n),空间复杂度O(1)。其中n为链表的长度。
面试题 19. 正则表达式匹配
面试题 21. 调整数组顺序使奇数位于偶数前面
class Solution {
public:
vector<int> trainingPlan(vector<int>& actions) { // 快慢指针
int low=0,fast=0; // low指向奇数存放的位置,fast向右寻找奇数
while(fast<actions.size()){
if(actions[fast]&1){ // 找到奇数
swap(actions[low],actions[fast]);
low++;
}
fast++;
}
return actions;
}
};
/*
定义快慢双指针 fast 和 low ,fast 在前, low 在后 .
fast 的作用是向前搜索奇数位置,low 的作用是指向下一个奇数应当存放的位置
fast 向前移动,当它搜索到奇数时,将它和 nums[low] 交换,此时 low 向前移动一个位置 .
重复上述操作,直到 fast 指向数组末尾 .
*/
面试题 22. 链表中倒数第 k 个节点
/**
* 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* trainingPlan(ListNode* head, int cnt) {
// 快慢指针,fast先走k步,fast到链尾时,slow就是倒数第k个节点
ListNode* slow=new ListNode(0,head);
ListNode* fast=new ListNode(0,head);
while(cnt--){ // fast指向第k个节点
fast=fast->next;
}
while(fast!=nullptr){
slow=slow->next;
fast=fast->next;
}
return slow;
}
};
面试题 24. 反转链表
/**
* 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* trainningPlan(ListNode* head) {
if(head==nullptr || head->next==nullptr){ return head;} // 链表为空或只有一个节点
ListNode* ans=trainningPlan(head->next); //递去: 深入链表,直到链尾,并返回链尾给ans,ans做反转后的表头节点
head->next->next=head; // 归来:反转指针
head->next=nullptr;
return ans;
}
/*
递归的时候是(head->next)->next, ((head->next)->next)->next, .... 这样递归直到链尾,没有改变head, head还是指向原来的头部。 head->1->2->...
- 归来:返回最深层时处理的是head<-1, 第一个指针;返回第一层的时候,处理的是最后一个和都是第一个的指针
*/
};
面试题 25. 合并两个排序的链表
/**
* 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* trainningPlan(ListNode* l1, ListNode* l2) {
if(l1==nullptr) return l2; // 递归终止条件,一个表空
if(l2==nullptr) return l1;
if(l1->val<=l2->val){
l1->next=trainningPlan(l1->next,l2);
return l1;
}else{
l2->next=trainningPlan(l1,l2->next);
return l2;
}
}
};
/*
通过递归,每次选择 l1 或 l2 中较小的节点加入合并链表,并更新该节点的 next 指针指向后续合并的结果。递归层层返回后,最终形成一个新的有序链表。
1. 特判:如果有一个链表为空,返回另一个链表
2. 如果l1节点值比l2小,下一个节点应该是l1,应该return l1,在return之前,指定l1的下一个节点应该是l1.next和l2俩链表的合并后的头结点
3. 如果l1节点值比l2大,下一个节点应该是l2,应该return l2,在return之前,指定l2的下一个节点应该是l1和l2.next俩链表的合并后的头结点
时间复杂度:O(m+n)
空间复杂度:O(m+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:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* dummy=new ListNode(0); // 虚拟头节点
ListNode* cur=dummy;
while(l1!=nullptr && l2!=nullptr){ // cur接上小的
if(l1->val <l2->val){
cur->next=l1;
l1=l1->next;
}else{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
cur->next = (l1 != nullptr ? l1 : l2); // 哪个表还没空,就接上剩余的
return dummy->next;
}
};
标签:ListNode,val,Day6,nullptr,next,l2,l1,Offer68
From: https://www.cnblogs.com/itsinsane/p/18518902