Leetcode - 160. 相交链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    // 假设A链表长度为5，B链表长度为3，那么可以定义两个指针curA和curB
    // curA从A链表的第3个节点出发，curB从B链表的第1个节点出发
    // 两个指针每次都向前走一步，两个指针第一次相遇的点即为相交的起始节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;

        // 计算两条链表的长度
        int lengthA = 1, lengthB = 1;
        while (curA.next != null) {
            curA = curA.next;
            lengthA++;
        }
        while (curB.next != null) {
            curB = curB.next;
            lengthB++;
        }

        // 如果两条链表的终点不同，则肯定不相交
        if (curA != curB) {
            return null;
        }
        
        // 如果链表B长度大于链表A，则交换两者的位置，保证headA指向的是长链表
        if (lengthA < lengthB) {
            ListNode temNode = headB;
            headB = headA;
            headA = temNode;

            int temLen = lengthA;
            lengthA = lengthB;
            lengthB = temLen;
        }


        // curA和curB指向各自链表的开头，并且curA先往前走lengthA - lengthB步
        curA = headA;
        curB = headB;
        for (int i = lengthA - lengthB; i > 0 ; i--) {
            curA = curA.next;
        }
        
        // 两个指针同时向前移动，直到指向相同的节点
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}