Leetcode.160.Intersection of Two

题目

给定两个单向链表, 链表可能从某个节点就指向同一个节点, 找出合并的节点.

Input:
a1 -> a2 -> a3 -> a4 -> a5 -> a6
b1 -> b2 -> a4 -> a5 -> a6
Output: 
a4 -> a5 -> a6

思路1

双循环.
时间复杂度O(n²)

ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB) {
    while(headB != nullptr) {
        ListNode *tempA = headA;
        while(tempA != nullptr) {
            if (tempA == headB) {
                return tempA;
            }
            tempA = tempA->next;
        }
        headB = headB->next;
    }

    return nullptr;
}

思路2

双指针, a指针先从A开始遍历, b指针先从B开始遍历, a遍历完A开始遍历B, b遍历完B开始遍历A, a和b走过的数量开始相等时即开始有相等的节点.
代码极其简单, 难以理解.
时间复杂度O(2m+2n)

ListNode *getIntersectionNode1(ListNode *headA, ListNode *headB) {
     ListNode* a = headA;
     ListNode* b = headB;
     while(a != b){
         a = a == NULL ? headB : a->next;
         b = b == NULL ? headA : b->next;
     }

  return b;
 }

思路3

先计算A和B的长度, 然后分别开始遍历, 当A和B剩下的节点数相等时, 开始查找相等的节点.
时间复杂度O(2m+2n)

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = 0, lenB = 0;
    ListNode* a = headA;
    ListNode* b = headB;
    while (a != nullptr) {
        a = a->next;
        lenA++;
    }
    while (b != nullptr) {
        b = b->next;
        lenB++;
    }

    while (headA && headB) {
        if (lenA > lenB) {
            headA = headA->next;
            lenA--;
        } else if (lenA < lenB) {
            headB = headB->next;
            lenB--;
        } else {
            break;
        }
    }

    while (headA && headB) {
        if (headA == headB) {
            return headA;
        } else {
            headA = headA->next;
            headB = headB->next;
        }
    }
    return nullptr;
 }

总结

单向节点的查找大多都是靠双指针, 快指针和慢指针, 左指针和右指针, 指针从a到b等方法.