Day12 双指针（简单）

Q1 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

/**
 * 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;
        else if (l2 == nullptr) return l1;

        ListNode *head = new ListNode(0);
        ListNode* p = head;
        
        while(l1 && l2)
        {   
            if(l1->val < l2->val)
              {  p->next = l1;
                 l1 = l1->next;
                 p = p->next;}
            else{
                 p->next = l2;
                 l2 = l2->next;
                 p = p->next;}
            }

        if (l1) p->next = l1;
        else p->next = l2;

        return head->next;
    }
};

Q2 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

主要思路： 先计算两个链表的长度，求差，利用差值使两个链表尾部对齐，从较短的链表头部位置开始遍历判断

当然，本题还有更加简洁的解法，使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。当它们相遇时，所指向的结点就是第一个公共结点。

剑指 Offer 52. 两个链表的第一个公共节点（双指针，清晰图解） - 两个链表的第一个公共节点 - 力扣（LeetCode） (leetcode-cn.com)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        int m=0,n=0;
        
        ListNode *q = headA,*p = headB;
        while(q!=nullptr)
        {
            q = q->next;
            m++;
        }
        while(p!=nullptr)
        {
            p = p->next;
            n++;
        }
        if(m==0||n==0) return nullptr;

        int d = abs(m-n);
        q = m>n ? headA : headB; 
        p = m>n ? headB : headA; 
        for(int i=0;i<d;i++)
             q = q->next;        
        while(p&&q)
        {
            if(q == p) return q;
            else{
                p = p->next;
                q = q->next;
            }
        }
        return nullptr;
    }
};

简洁：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};