您现在的位置是：首页 >技术交流 >剑指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->val<cur2->val)
            {
                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(lenA<lenB)
        {
            while(ret)
            {
                curB=curB->next;
                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<int> exchange(vector<int>& nums)
    {
        vector<int> arr1;
        vector<int> 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<int> twoSum(vector<int>& nums, int target) 
    {
        int left=0;
        int right=nums.size()-1;
        vector<int> 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]<target)
                    {
                        left++;
                    }
                    else
                    {
                        ch.push_back(nums[left]);
                        ch.push_back(nums[right]);
                        return ch;
                    }

                }
                //return nullptr;
            }
        }
        return ch;
    }
};

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<string> 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;
    }
};