题目描述

解题思路

详细见专题链表。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // ListNode node1 = headA;
        // ListNode node2 = headB;
        // int lengthA = 0;
        // int lengthB = 0;
        // while (node1 != null) {
        //     node1 = node1.next;
        //     lengthA++;
        // }
        // while (node2 != null) {
        //     node2 = node2.next;
        //     lengthB++;
        // }
        // node1 = headA;
        // node2 = headB;
        // if(lengthB > lengthA) {
        //     // 交换长度
        //     int temp = lengthA;
        //     lengthA = lengthB;
        //     lengthB = temp;
        //     // 交换节点
        //     ListNode tempNode = node2;
        //     node2 = node1;
        //     node1 = tempNode;
        // }
        // int gap = lengthA -lengthB;
        // while(gap-- > 0) {
        //     node1 = node1.next;
        // }
        // while(node1 != null) {
        //     if(node1 == node2) return node1;
        //     node1 = node1.next;
        //     node2 = node2.next;
        // }
        // return null;
        ListNode node1 = headA;
        ListNode node2 = headB;
        int lengthA = 0;
        int lengthB = 0;
        while (node1 != null) {
            node1 = node1.next;
            lengthA++;
        }
        while (node2 != null) {
            node2 = node2.next;
            lengthB++;
        }
        // 注意要重新把头节点赋给他
        node1 = headA;
        node2 = headB;
        int num = Math.abs(lengthA - lengthB);
        if (lengthA > lengthB) {
            while (num-- > 0) {
                node1 = node1.next;
            }
        } else {
            while (num-- > 0) {
                node2 = node2.next;
            }
        }
        while (node1 != null && node2 != null) {
            if (node1 != node2) {
                node1 = node1.next;
                node2 = node2.next;
            }else {
                return node1;
            }
        }
        return null;
    }
}