剑指offic--双指针
PS：以下代码均为C++实现
1.删除链表的节点 力扣
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof
//单指针做法
class Solution
{
public:ListNode* deleteNode(ListNode* head, int val) {ListNode* cur=head;while(cur&&cur->next!=nullptr){//如果头结点为要删除的节点，则直接删除头结点if(cur->val==val){cur=cur->next;head=cur;}//不是头结点的，则遍历一遍，直到找到要删除的节点位置，删除else if((cur->next->val==val)&&cur->next!=nullptr){cur->next=cur->next->next;}//不是，则向下移动else{cur=cur->next;}}return head;}
};
//双指针做法，创建两个头结点，一个指向头结点，另一个指向头节点的前一个位置
class Solution
{
public:ListNode* deleteNode(ListNode* head, int val) {//头结点为要删除的节点if(head->val == val) return head->next;//其他情况ListNode *pre = nullptr, *cur = head;while(cur != nullptr && cur->val != val) {pre = cur;cur = cur->next;}if(cur != nullptr) pre->next = cur->next;return head;}
};
2.链表中倒数第K个节点 力扣
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
//1.双指针。定义两个指针，一个快指针，一个慢指针，快指针先走k个位置，慢指针再走，快指针走完后慢指针//的位置就是第K个位置
class Solution
{
public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode* fast=head;while(k){fast=fast->next;k--;}ListNode* slow=head;while(fast){fast=fast->next;slow=slow->next;}return slow;}
};//2.单指针，计算链表的长度，然后走到第K个结点的时候，返回
class Solution
{
public:ListNode* getKthFromEnd(ListNode* head, int k){int i=0;ListNode* cur=head;while(cur){i++;cur=cur->next;}ListNode* prevtail=nullptr;ListNode* prevhead=nullptr;cur=head;while(i--){if(i+1==k){while(cur){if(prevhead==nullptr){prevhead=prevtail=cur;}else{prevtail->next=cur;prevtail=prevtail->next;}cur=cur->next;}return prevhead;}else{cur=cur->next;}}return nullptr;}
};
3.合并两个排序的链表 力扣
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
// 迭代遍历一遍，使用不带哨兵位的头结点，这道题十分简单，不过多说明
class Solution
{
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1==nullptr&&l2==nullptr)return nullptr;if(l1==nullptr)return l2;if(l2==nullptr)return l1;ListNode* prevhead=nullptr;ListNode* prevtail=nullptr;ListNode* cur1=l1;ListNode* cur2=l2;while(cur1&&cur2){if(cur1->valval){if(prevtail==nullptr){prevtail=prevhead=cur1;cur1=cur1->next;}else{prevtail->next=cur1;cur1=cur1->next;prevtail=prevtail->next;}}else{if(prevtail==nullptr){prevtail=prevhead=cur2;cur2=cur2->next;}else{prevtail->next=cur2;cur2=cur2->next;prevtail=prevtail->next;}}}if(cur1!=nullptr){while(cur1){prevtail->next=cur1;cur1=cur1->next;prevtail=prevtail->next;}}if(cur2!=nullptr){while(cur2){prevtail->next=cur2;cur2=cur2->next;prevtail=prevtail->next;}}while(cur1||cur2)prevtail->next=cur1==nullptr?cur1:cur2;return prevhead;}
}; 4.两个链表的第一个公共节点 力扣
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
//使用两个头结点遍历两个链表，判断连个链表的长度，让长的先走两个链表的长度之差，然后两个一起走，直到//遇到相同的指针停下，返回这个节点
class Solution
{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int lenA=0;int lenB=0;ListNode* curA=headA,*curB=headB;while(curA){curA=curA->next;lenA++;}while(curB){curB=curB->next;lenB++;}curA=headA;curB=headB;int ret=abs(lenA-lenB);if(lenA>lenB){while(ret){curA=curA->next;ret--;}}else if(lenAnext;ret--;}}while(curA){if(curA==curB){return curA;}curA=curA->next;curB=curB->next;}return nullptr;}
}; 5.调整数组顺序使奇数位于偶数前面 力扣
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
//这道题方法很多，请自行选择
class Solution
{
public:vector exchange(vector& nums){vector arr1;vector arr2;int a = 0;int b = 0;for (int i = 0; i < nums.size(); i++){if (nums[i] % 2 == 0){arr2.push_back(nums[i]);a++;}else{arr1.push_back (nums[i]);b++;}}int len1 = arr1.size();for (int i = len1; i < nums.size(); i++){arr1.push_back(arr2[i - len1]);}return arr1;}
}; 6.和为S的两个数字 力扣
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof
//这道题使用头尾指针来做，先判断最后的数是否大于S，如果大于则尾指针--，直到遇到比S小或等于的数字停//下来，然后和头指针的数字相加，如果大于，则尾指针继续--，然后与头指针相加，直到遇到一个与S相同的和
class Solution {
public:vector twoSum(vector& nums, int target) {int left=0;int right=nums.size()-1;vector ch;int min=0;while(right>0){if(nums[right]>target){right--;}else{while(left<=right){if(nums[right]+nums[left]>target){right--;}else if(nums[right]+nums[left] 7.翻转单词的顺序 力扣
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof
//单指针
class Solution {
public:string reverseWords(string s) {// 反转整个字符串reverse(s.begin(), s.end());int n = s.size();int idx = 0;for (int start = 0; start < n; ++start) {if (s[start] != ' ') {// 填一个空白字符然后将idx移动到下一个单词的开头位置if (idx != 0) s[idx++] = ' ';// 循环遍历至单词的末尾int end = start;while (end < n && s[end] != ' ') {s[idx++] = s[end++];}// 反转整个单词reverse(s.begin() + idx - (end - start), s.begin() + idx);// 更新start，去找下一个单词start = end;}}s.erase(s.begin() + idx, s.end());return s;}
};
//双指针
class Solution {
public:string reverseWords(string s) {int left = 0, right = s.size() - 1;// 去掉字符串开头的空白字符while (left <= right && s[left] == ' ') ++left;// 去掉字符串末尾的空白字符while (left <= right && s[right] == ' ') --right;deque d;string word;while (left <= right) {char c = s[left];if (word.size() && c == ' ') {// 将单词 push 到队列的头部d.push_front(move(word));word = "";}else if (c != ' ') {word += c;}++left;}d.push_front(move(word));string ans;while (!d.empty()) {ans += d.front();d.pop_front();if (!d.empty()) ans += ' ';}return ans;}
}; 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！