题解
方法一:龟兔赛跑
最先想到的方法,姑且叫它“龟兔赛跑”:先计算两条LinkedList的长度,然后让长的那条先走,直到剩下的节点数一样,相当于回到同一起跑线。接下来,以同样的步调向后遍历并比较节点。代码写起来不是很简洁,但是并不影响复杂度,能通过。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode* node = headA;
while (node) {
node = node->next;
lenA++;
}
node = headB;
while (node) {
node = node->next;
lenB++;
}
if (lenA >= lenB) {
while (lenA > lenB) {
headA = headA->next;
lenA--;
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
else {
while (lenB > lenA) {
headB = headB->next;
lenB--;
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
}
};
方法二:首尾相接制造环
对于两条不同长度的链表,可以进行首尾相接,制造一个环,这样,新的链表长度一样,可以省去上面方法中需要计算长度的步骤。也就是说,链表1的尾部与链表2的首部相接,再把链表2的尾部接回链表1的首部;另一边反之,从链表2的尾部接到链表1的首部,再接回链表2的首部,得到另一条新的链表。
下面的代码是参考别人的代码,已经非常简洁。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};