[数据结构与算法]LeetCode 160-相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。

解题思路：

定义两个指针分别指向两个链表的头部, 首先让两个指针向后移动，让先移动到末尾的指针从另一个链表的头部再次移动，
最后如果相遇则为交点。
原理：在第一轮移动中恰好抹除了长度差，两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    	// 1. 边界条件
        if(headA == null || headB == null) {
            return null;
        }
        // 2. 两个指针指向两个链表的头部
        ListNode head1 = headA;
        ListNode head2 = headB;
		// 3. 两个指针开始移动
		// 离开循环的条件：
		// 1.两个链表没有相交，两指针都会移动到末尾，head1 = head2 = null
		// 2.两个链表没有相交，head1 = head2 = 相交点
        while (head1 != head2) {
            if (head1 != null) {
                head1 = head1.next;
            } else {
                head1 = headB;
            }

            if (head2 != null) {
                head2 = head2.next;
            } else {
                head2 = headA;
            }
        }
        return head1;
    }
}

时间复杂度：O(m+n)，其中 m 和 n 是两个链表的长度
空间复杂度：O(1)

如果对您有所帮助的话，请点个赞再退出吧！！！

题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/添加链接描述