LeetCode题解-160. 相交链表

发表于 分类于

题目描述

编写一个程序，找到两个单链表相交的起始节点。

思路

除了暴力法之外，可以用双指针法来做。

创建两个节点l1和l2，分别指向两个链表heabA和headB的头，然后依次向后遍历，并判断两个节点是否相等，相等且都不为空，则表示有相交。如果l1到达链表的尾部，则把l1指向headB；如果l2到达链表的尾部，则把l2指向headA。

证明

LeetCode题解-160-相交链表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            if (l1 == null) {
                l1 = headB;
            } else {
                l1= l1.next;
            }
            if (l2 == null) {
                l2 = headA;
            } else {
                l2 = l2.next;
            }
        }
        return l1;
    }