[做题]双指针

第一天刷题。一个平实的开始，希望能坚持下来，不求波涛汹涌，大浪淘沙，但求静水流深，川流不息。

先学习双指针。题目方向分为两个：链表和数组。

在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。

所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。

文章目录

- - 链表中的双指针
- 第一道：21.合并两个有序链表
- 第二道：分割链表
- 第三道：合并K个升序链表
- 第四道：单链表的倒数第 k 个节点
- 第五道：链表的中间结点
- 第六道：相交链表
- 第七道：判断是否为环形链表
- 第八道：找到环形链表的起点
- - 数组中的双指针
- 第一道： [删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)
- 第二道：移除元素
- 第三道:移动零
- 第四道：最长回文子串

链表中的双指针

第一道：21.合并两个有序链表

思路一：申请第三个链表的空间，拷贝两个链表中较小的一个。

代码v1.0：

class Solution {
public:
    bool comp(ListNode* l1, ListNode* l2){
        if(l1->val > l2->val) return true;
            else return false;
    }
    bool Empty_Judge(ListNode* l){
        if(l->val==0) return true;
            else return false;
    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(Empty_Judge(list1)) return list2;
        if(Empty_Judge(list2)) return list1;
        ListNode* list ;
        ListNode* head = list;
        while(list1!=nullptr&&list2!=nullptr)
        {
            list = new ListNode;
            if(comp(list1,list2)){
                list->val = list2->val;
                list = list->next;
                list2 = list2->next;
            }
            else{
                list->val = list1->val;
                list = list->next;
                list1 = list1->next;
            }
        }
        while(list1!=nullptr){
            list = new ListNode(list1->val);
            list=list->next;
            list1=list1->next;
        }
        while(list2!=nullptr){
            list = new ListNode(list2->val);
            list=list->next;
            list2=list2->next;
        }
        return head;
    }

};

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

问题：返回的 head 没有任何数值。

解决：

链表到下一个结点前需要空间，否则指向NULL就是野指针，也就不可能连上。

代码开始，head 指向了没有初始化的 list ，即指向一个（指向null的）野指针，它自己也变成了野指针。如果初始化工作做好，不解决后续连接过程的“先申请空间，再连接”，就会只有一个数据。
条件判断分不清 NULL 、nullptr 及其背后的 true 、false，造成代码冗余。

Empty_judge 和 comp 函数是完完全全的多余代码，因为本可以直接在原代码中判断。

代码V2.0：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        ListNode* list = new ListNode ;
        ListNode* head = list;
        while(list1&&list2)
        {
            if(list1->val > list2->val){
                list->val = list2->val;
                list2 = list2->next;
            }
            else{
                list->val = list1->val;
                list1 = list1->next;
            }
            list->next = new ListNode;
            list = list->next;
        }

        while(list1)
        {
            list ->val = list1 -> val;
            if(list1->next) list->next = new ListNode;
            list=list->next;
            list1=list1->next;
        }
        while(list2)
        {
            list ->val = list2 -> val;
            if(list2->next) list->next = new ListNode;
            list=list->next;
            list2=list2->next;
        }

        return head;
    }

};

规避了野指针问题和相对的代码冗余问题。

思路二：在两个指针现有的空间上，只做穿针引线的工作（连接起来）

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;   //可以省略
        if(!list2) return list1;
        ListNode* list = new ListNode;
        ListNode* head = list;
        while(list1&&list2)
        { 
            if(list1->val > list2->val){
                list -> next = list2;
                list = list2;  //这里可以配合下面简化
                list2 = list2->next;
            }
            else{
                list -> next = list1;
                list = list1;  //简化
                list1 = list1->next;
                //list = list->next
            }
        }
        list -> next = list1 ? list1 : list2;  
        return head -> next;
    }

问题：

开始的判断是否为空可以省略。
while 中出现重复点（只是需要一点点直觉）

解决：

看思路三。

**思路三：**labuladong ，虚拟头结点值得注意。整体与思路二没什么区别。

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
    // 比较 p1 和 p2 两个指针
    // 将值较小的的节点接到 p 指针
    if (p1.val > p2.val) {
        p.next = p2;
        p2 = p2.next;
    } else {
        p.next = p1;
        p1 = p1.next;
    }
    // p 指针不断前进
    p = p.next;
}

if (p1 != null) {
    p.next = p1;
}

if (p2 != null) {
    p.next = p2;
}

return dummy.next;

}

代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，如果不使用 dummy 虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

拓展：

思路四：递归

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
    if(l1->val < l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}

类似汉诺塔的思路。

第二道：分割链表

V1.0

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        //初始化
        ListNode* tail = head;
        while(tail->val < x )  tail=tail->next;
        ListNode* temp = tail;
        ListNode* maxdot = tail;//大于值开始的结点
        while(head->val > x) head = head->next;
        tail = head; //小于值开始的结点

        
        while(temp)
        {
         //<x
            if(temp->val < x){  //如果是小于值结点
                tail ->next = temp;
                tail = tail->next;
            }
            
        //>x
            if(temp->val >x &&temp->next->val < x ){
                tail->next = temp->next;
                if(temp->next->next)  temp->next = temp->next->next;
                else {
                    tail->next = temp->next;
                    temp->next = nullptr;
                    break;
                }
            }
            temp = temp->next;
        }
        tail->next = maxdot;
        return head;
    }
};

现在思路也不是很清晰

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

思路二：双头结点

ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode* dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode* dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode* p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode* p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;

    return dummy1.next;
}

创建两个头结点，先断开，后连接。

思路三：递归

class Solution {
public:
    ListNode* small = nullptr;
    pair<ListNode*, ListNode*> helper(ListNode* head, int x) {
        if (head == nullptr) return make_pair(nullptr, nullptr);
        if (head->val < x) small = head;
        pair<ListNode*, ListNode*> next = helper(head->next, x);
        if (head->val < x) {
            head->next = next.first;
            next.first = head;
        }
        else {
            head->next = next.second;
            next.second = head;
        }
        return next;
    }
    ListNode* partition(ListNode* head, int x) {
        pair<ListNode*, ListNode*> nodes = helper(head, x);
        if (nodes.first) {
            small->next = nodes.second;
            return nodes.first;
        }
        else {
            return nodes.second;
        }
    }
};

大多数链表题递归的时候可以无脑写一句，然后只要让思路从后向前进行就可以了。

cppListNode* node = func(head->next);  // func为递归函数

这里返回值选择了两个pair，first保存小于x的结点，second保存大于x的结点。

思路四:原地连接

// 1 4 3 2 5 2 
struct ListNode* partition(struct ListNode* head, int x){
    if(!head || !head->next){
        return head;
    }
    struct ListNode *p = head, *q = head, *temp = NULL;
    if(p->val < x){ 
        while(p->next->val < x){//此循环让 p 到达最远小值  1
            p = p->next; 
            if(p->next == NULL){
                return head;
            }
        }
        q = p->next;   //让 q 到达最近大值  4
    }
    else{
        p = NULL;  
    }
    while(q->next){ //q存在下一个结点
        if(q->next->val < x){  //如果最近大值下一个为小值
            temp = q->next; //temp为小值了
            q->next = temp->next;//跳过小值
            
            if(p == NULL){ //如果起始值为大值（即p 为空情况）
                temp->next = head; //头插法：第一个插入的小值连接起始大值
                head = temp;
                p = head;
            }
            else{//起始值小值（存在了）
                temp->next = p->next; //头插法：小值后
                p->next = temp;
                p = temp;
           }
        }
        else{ //为大值就串下去
            q = q->next;
        }
    }
    return head;
}

p指针指向小于 x 的值，p == null 就连接第一个大于x的值，p!=null 就按顺序进行尾插法；
(只是 p 的"尾"是 q 的"头")
q指针指向大于 x 的值，初始是第一个大于x的值，尾插法依次往后放;
temp 服务于p的尾插法，作为中间变量。
（q 尾插循环的前面，是p,q 的初始化工作，分别指定小于x值的尾端和大于x值的尾端）

第三道：合并K个升序链表

思路一：遍历合并两个链表到第一个链表中去

class Solution {
public:
    ListNode* merge(ListNode* list1,ListNode* list2) //这里和合并有序链表的code一模一样
    {...}
    ListNode* mergeKLists(vector<ListNode*>& lists) {//遍历合并
        if(lists.empty()) return nullptr;
        vector<ListNode*>::iterator it = lists.begin();
        vector<ListNode*>::iterator next = lists.begin()+1;
        for(;next!=lists.end();next++){
            *it = merge(*it,*next);
        }
        return *it;
    }
};

**思路二：**labladong ：配合优先队列的二叉堆，获取最小k结点

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode*> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

思路三：分治递归

class Solution {

    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

思路四：STL中的优先队列

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto head = ListNode(0);
        auto comp = [](ListNode* const &a, ListNode* const &b){return a->val > b->val;};
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);
        for (auto &h : lists) if (h != nullptr) q.push(h);
        auto p = &head;
        while (!q.empty()) {
            p->next = q.top();
            p = p->next;
            q.pop();
            if (p->next != nullptr) q.push(p->next);
        }
        return head.next;
    }
};

第四道：单链表的倒数第 k 个节点

ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(n==0||!head) return head;    //0元素 或 不动
        if(!head->next) return NULL;    //1元素 且 动
        ListNode* fformer = head;
        ListNode* former = head;
        ListNode* latter = head;
        while(--n>0) latter = latter->next;
        while(latter->next)
        {
            if(former!=head) fformer = fformer->next;
            latter = latter -> next;
            former = former -> next;
        } 
                         //1元素
        if(former == fformer) head = former->next; //2元素
        else fformer->next = former->next;   //3+元素
        return head;

第五道：链表的中间结点

    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next)
        {
            fast = fast->next;
            if(fast->next) fast=fast->next;
            slow = slow->next;
        }
        return slow;
    }

第六道：相交链表

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

这个赋值和 ？条件判断的配合非常有趣。

简短的 if 语句可用？来代替。

思路二：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    // 计算两条链表的长度
    for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
        lenA++;
    }
    for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    ListNode p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

第七道：判断是否为环形链表

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

不解释

第八道：找到环形链表的起点

流程起始同上，先让快慢指针相遇。

设相遇点距离头结点为 k ,即慢指针的路程。快指针速度是慢指针二倍，路程即 k+k=2k
设环形起点距离相遇点为 m , 则慢指针距离起点 k-m。巧合的是，相遇点指针不断向后走，距离起点同样为k-m 。
所以让其中任意一个指针回到起点，经过k-m位移，另一个指针就会到达环形链表起点。

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;
    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

数组中的双指针

在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧。

第一道：删除有序数组中的重复项

基本的快慢双指针。

int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
}

大同小异的一个链表题：

删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/)

struct ListNode* deleteDuplicates(struct ListNode* head){
        typedef struct ListNode ListNode;
        if(!head) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast)
        {
            if(fast->val!=slow->val)
            {
                slow=slow->next;
                slow->val=fast->val;
            }
            fast=fast->next;
        }
        slow->next = NULL;
        return head;

第二道：移除元素

左右指针：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int j = nums.size() - 1;
        for (int i = 0; i <= j; i++) {
            if (nums[i] == val) {
                swap(nums[i--], nums[j--]);
            }
        }
        return j + 1;
    }
};

快慢指针：

    while(fast<numsSize)
    {
        if(nums[fast]!=val)
        {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;

扩展：保留重复k个元素的基础上删除多余元素

class Solution {
public:
 int work(vector<int>& nums, int k) {
     int len = 0;
     for(auto num : nums)
         if(len < k || nums[len-k] != num)
             nums[len++] = num;
     return len;
 }
 int removeDuplicates(vector<int>& nums) {
     return work(nums, 2);
 }
};

第三道:移动零

v1.0

    void moveZeroes(vector<int>& nums) {
        int fast = 0,slow=0;
        while(fast<nums.size())
        {
            if(nums[fast]!=0){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        while(slow<fast){
            nums[slow++]=0;
        }
    }

v2.0

        int left = 0;
        int right = 0;
        while(right < nums.size())
        {
            if(nums[right])
            {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }

遇到非0直接交换就可以

第四道：最长回文子串

  string longestPalindrome(string s) {
        string res = "";
        for(int i=0;i<s.size();i++)
        {
            string s1=palindrome(s,i,i);
            string s2=palindrome(s,i,i+1);
            res = s1.size()>res.size()?s1:res;
            res = s2.size()>res.size()?s2:res;
        }
        return res;
    }
    string palindrome(string s,int l,int r)
    {
        while(l>=0&&r<s.size()&&s[l]==s[r])
        {
            l--;
            r++;
        };
        return s.substr(l+1,r-l-1);
    }