[Leetcode] Intersection of Two Linked Lists 链表交点

双指针法

复杂度

时间 O(N) 空间 O(1)

思路

先算出两个链表各自的长度，然后从较长的链表先遍历，遍历到较长链表剩余长度和较短链表一样时，用两个指针同时遍历两个链表。这样如果链表有交点的话，两个指针已经一定会相遇。

代码

public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        ListNode nodea = headA, nodeb = headB;        int lena = 0, lenb = 0;        // 计算链表A的长度        while(nodea != null){lena++;nodea = nodea.next;        }        // 计算链表B的长度        while(nodeb != null){lenb++;nodeb = nodeb.next;        }        // 让较长的链表先飞一会        for(int i = 0; i < Math.abs(lena - lenb); i++){if(lenb > lena) headB = headB.next;else if(lena > lenb) headA = headA.next;        }        while(headA != null && headB != null){if(headA == headB) return headA;headA = headA.next;headB = headB.next;        }        return null;    }}