博客

双指针思想

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的 。

双指针是很多算法的基础，如

归并排序、滑动窗口、字符匹配（左右括号匹配）

等。

滑动窗口即维持一段区间。

在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。比单个指针来回移动的效率从o(n2)提高到o(n)。

算法框架

for(int i = 0, j = x; i < n; i++)
{
   
    // step1: j范围有效 & 设计某个性质，使的j具有某种单调性
    while(j < m && check(i, j)) jxx

    // step2：这道题目的具体逻辑

    // step3: 这里注意i，j的更新！！
}

力扣双指针类型集合

可以参考滑动窗口类型集合题目一起学习，两者有重叠

1、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
   
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
   
        if(l1 == nullptr)
            return l2;
        if(l2 == nullptr)
            return l1;
        ListNode* pTemp = new ListNode(0);
        ListNode* pHead = pTemp;
        while(l1 != nullptr && l2 != nullptr)
        {
   
            if(l1->val > l2->val)
            {
   
                pTemp->next = l2;
                pTemp = l2; 
                l2 = l2->next;
            }
            else
            {
   
                pTemp->next = l1;
                pTemp = l1;
                l1 = l1->next; 
            }
        }
        if(l1 == nullptr)
            pTemp->next = l2;
        if(l2 == nullptr)
            pTemp->next = l1;
        
        return pHead->next;
    }
};

2、删除排序链表中的重复元素 –简单

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
   
public:
    ListNode* deleteDuplicates(ListNode* head) {
   
        if(!head)
            return nullptr;
        
        ListNode* pre = head;
        ListNode* cur = head->next;
        while(cur)
        {
   
            if(cur->val != head->val)
            {
   
                head->next = cur;
                head = cur;
            }
            
            cur = cur->next;