160. Intersection of Two Linked Lists

原题链接：https://leetcode.com/problems/intersection-of-two-linked-lists/description/
这道题目貌似没说这两个单链表是排序的，刚开始我以为是排序的单链表呢，然后我写下了如下的答案，并且通过了。。。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        while ((headA.next != null || headB.next != null) && headA != headB) {
            if (headA.val < headB.val) {
                if (headA.next != null) {
                    headA = headA.next;
                } else {
                    break;
                }
            } else {
                if (headB.next != null) {
                    headB = headB.next;
                } else {
                    break;
                }
            }
        }
        return headA == headB ? headA : null;
    }
}

然后，我去看了下官方的解答才知道这道题目并没有说这两个单链表是排序链表呢！那么，没有排序的两个链表该怎么处理呢？官方给出了三种解答：

1. 双层循环进行暴力遍历
2. 基于第一种方法，使用哈希表来加快查找速度
3. 官方解释我是没看懂，说是用两个指针的方法。。不过下面别人贴的代码我倒是看懂了

int getListLength(ListNode* head) {
    int len = 0;
    while (head) {
        ++len;
        head = head->next;
    }
    return len;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr) {
        return nullptr;
    }
    int ALen = getListLength(headA);
    int BLen = getListLength(headB);
    if (ALen < BLen) {
        std::swap(ALen, BLen);
        std::swap(headA, headB);
    }
    for (int i = 0; i < ALen - BLen; ++i) {
        headA = headA->next;
    }
    for (int i = 0; i < BLen; ++i) {
        if (headA == headB) {
            return headA;
        }
        headA = headA->next;
        headB = headB->next;
    }
    return nullptr;
}