leetcode 160. 相交链表 (判断链表是否相交)

leetcode 160. 相交链表 (判断链表是否相交)

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

img

方法一：计算两个链表的差，让长的先走m-n步，然后一起走，如果后面相交则p1 == p2，否则各自走到链尾

/**
 * 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) {
        ListNode* p1 = headA;
        ListNode* p2 =headB;
        int lenA = 0;
        int lenB = 0;
        while(p1) {
            ++lenA;
            p1 = p1->next;
        }
        while(p2) {
            ++lenB;
            p2 = p2->next;
        }
        p1 = headA; //注意重置指针，要不就是操控空指针
        p2 = headB;
        int num = abs(lenA-lenB);
        if(lenA > lenB) {
            while(num--) {
                p1 = p1->next;
            }
        }
        else {
            while(num--) {
                p2 = p2->next;
            }
        }
        while(p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};

方法二：走位自己的链表后返回走另一个，第二圈时如果相遇则p1==p2,否则两个两个一起走到链尾p1=nullptr,p2 = nullptr

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        while(p1 != p2) {//找不到p1走n+m,p2走m+n，同时为nullptr;找到则p1==p2
            if(p1) {
                p1 = p1->next;
            }
            else {	// p1 走一步，如果走到 A 链表末尾，转到 B 链表
                p1 = headB;
            }

            if(p2) {
                p2 = p2->next;
            }
            else {	// p2 走一步，如果走到 B 链表末尾，转到 A 链表
                p2 = headA;
            }
        }
        return p1;
    }
};

• 时间复杂度：O(m+n)，其中m 和 n是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

• 空间复杂度：O(1)。