leetcode-160

题目

• 如果两个链表没有交点，返回 null.

• 在返回结果后，两个链表仍须保持原有的结构。

• 可假定整个链表结构中没有循环。

• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

一解

/** * 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) {        if(headA == null || headB == null) {            return null;        }        for(ListNode p = headA; p != null; p = p.next) {            for(ListNode q = headB; q != null; q = q.next) {                if (p == q) {                    return p;                }            }        }        return null;    }}

二解

a = [1, 3, 5, 7, 9, 11]
b = [2, 4, 9, 11]

c = [1, 3, 5, 7, 9, 11, 2, 4, 9, 11]
d = [2, 4, 9, 11, 1, 3, 5, 7, 9, 11]

• 链表长度一致（a + b = b + a）

• 尾端（交叉端一致）即 [9, 11] 这一段
因为链表是前部不一致，后部交叉到一起，所以无论以什么顺序连接，两链表的最尾端总是一样的

/** * 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) {        if(headA == null || headB == null) {            return null;        }        ListNode p = headA;        ListNode q = headB;        while(p != q) {            p = p != null ? p.next: headB;            q = q != null ? q.next: headA;        }        return p;    }}

a = [1, 3, 4]
b = [2, 4, 5, 6]