leetcode160–相交链表（最优解/双指针）

今天做的三道题比较简单～

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

这道题注意思路，尽量简洁代码，对照官方答案，是我不配了……
先附上不优雅的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *s = (struct ListNode *)malloc(sizeof(struct ListNode)*1);
    struct ListNode * a, * b,* a_x,* b_x;
    a = headA;
    b = headB;
    int len = 0;
    int flag = 1;
    while(a != NULL && b != NULL)
    {
        a = a->next;
        b = b->next;
    }
    while(a!= NULL)
    {
        len++;
        flag = 1;
        a = a->next;
    }
    while(b!= NULL)
    {
        len++;
        flag = 0;
        b = b->next;
    }
    a_x = headA;
    b_x = headB;
    while(len > 0)
    {
        if(flag == 0)
        {
            b_x  = b_x->next;
        }
        else
        {
            a_x = a_x->next;
        }
        len--;
    }
    while(a_x != NULL)
    {
        if(a_x == b_x)
        {
            return a_x;
        }
        else
        {
            a_x = a_x -> next;
            b_x = b_x -> next;
        }
    }
    return NULL;
}

优雅代码在这里
思路：就是两个指针一个指a一个指b，a走完了重新指到b，b走完了指到a。如果不相交，那两个指针就是把两个链表都走了一遍，最后都指向空。如果相交，那交的那一部分长度相同，第二次在相交的时候一定能碰到。因为最终两指针走的一样远。

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

虽然官方代码简洁 我还是觉得我的好