想法一
一一对比，假设用a1和链表B中所有节点比较，找不到，再用a2……直到A最后比较完
时间复杂度：O(N*M) 空间复杂度：O(1)
想法二
算出两个链表长度，让长链表的头指针走差距步，然后两个链表指针同时边走边比对
先用tail1和tail2指针找尾，算出各自链表的长度
再比较尾节点的地址是否相等，如果相等，则链表相交，如果不相等，返回NULL
注意：比较的是两个节点的地址，而不是存储的数值
接着，创建长表头和短表头指针 ，让longlist指针先走差距步
最后，两个指针同时向后走，一旦地址相同则停下，返回相交节点的地址
时间复杂度：O(N) 空间复杂度：O(1)
完整代码如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *tail1 = headA, *tail2 = headB; int len1 = 1, len2 = 1; while (tail1->next) { tail1 = tail1->next; len1++; } while (tail2->next) { tail2 = tail2->next; len2++; } if (tail1 != tail2) { return NULL; } int gap = abs(len1 - len2); struct ListNode *longlist = headA, *shortlist = headB; if (len1 < len2) { longlist = headB; shortlist = headA; } while (gap--) { longlist = longlist->next; } while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; }
