[LeetCode]求两个链表的焦点--Intersection of Two Linked Lists

1.解题意

求解两个链表的焦点，这个交点并不是焦点的值相等，而是需要交点之后的数据是完全相等的。

落实到java层面，就是交点处的对象是同一个对象即可。

ps：我最开始没有读懂题目，然后就开始比较节点的值是否相等，直到示例跑失败了才知道原因。

2.通用解法

	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA!=null && headB!=null){

            ListNode tempA=headA;

            ListNode tempB=headB;

            while(tempA!=null){

                while(tempB!=null){

                    if(tempA==tempB){

                        return tempA;

                    }

                    tempB=tempB.next;

                }

                tempB=headB;

                tempA=tempA.next;

            }

        }

        return null;

    }

这里通过双循环的方式来遍历每一个节点，如果节点是同一个对象即可返回，这是我们正常的思维。

接下来的结果就打脸了：时间复杂度|空间复杂度超过5%的解法。

哎，还是读题的问题，题目要求了时间复杂度是 O(n)，空间复杂度是O(1);那么应该是有更优解的。

3.更优解

首先，假定存在交点，交点之后的链表长度是 c，链表A在交点之前的长度是a，链表B在交点之前的长度是b；

A的长度是 a+c；B的长度是 b+c

如果我们让两边相等，即把长度变成是 a+b+c，那么链表A的最后一个节点是链表B交点之前的节点，即下一个节点就是交点；同理链表B的最后一个节点的下一个节点就是交点；

这样，我们可以只遍历一次，就可以找到交点，最大的长度是 a+b+c+1，即可找到交点；

代码如下：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode l1 = headA, l2 = headB;

        int finishA = 0;

        boolean finishB = false;

        while (l1 != l2 && finishA<3) {

            if(l1==null){

                finishA++;

            }

            if(l2==null){

                finishA++;

            }

            l1 = (l1 == null) ? headB : l1.next;

            l2 = (l2 == null) ? headA : l2.next;

        }

        return finishA>=3?null:l1;  // 修改当无交点时的死循环

    }

参考：https://cyc2018.github.io/CS-Notes/#/notes/Leetcode 题解 - 链表

巴特西

[LeetCode]求两个链表的焦点--Intersection of Two Linked Lists

1.解题意

2.通用解法

3.更优解

最新文章

热门文章