LeetCode 160——相交链表（JAVA）

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

如下面的两个链表：

在节点 c1 开始相交。

示例 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 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

在解题之前我发现了一个问题：示例一中相交链表的起始节点是8，而不是1，经过仔细思考，才理解。

这里的相交不是指值一样，而是指占用同一片内存空间，完全是一样的。这点在解题的时候至关重要！！！！一旦找到了一个这样的节点，那么之后两个链表的节点对应着也就占用相同的内存空间，就无需判断了。这是因为由链表的性质决定的，node.next只有一个。

先上来代码：

/**

 * 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;

    }

    int lengthA=;

    int lengthB=;

    ListNode node1=headA;

    ListNode node2=headB;

    ListNode result=null;

    while(node1!=null)

    {

        lengthA++;

        node1=node1.next;

    }

   while(node2!=null)

    {

        lengthB++;

        node2=node2.next;

    }

    node1=headA;

    node2=headB;

    while(lengthA>lengthB)

    {

        node1=node1.next;

        lengthA--;

    }

    while(lengthA<lengthB)

    {

        node2=node2.next;

        lengthB--;

    }

    //此时node1 node2已经指向了合适的位置，确保到尾节点的长度是一样的。

    while(true)

    {

        if(node1==node2)//这里nowA==nowB意味着从该节点之后所有链表节点都是公用的，尤其要理解题意，这里的相交不只是指链表中的值相同，而是链表中的元素就是同一块内存空间，一旦找到了同一块内存，那么之后的链表也一定是同一块内存。

        {

            result=node1;

            break;

        }

        if(node1==null||node2==null)

        {

            break;

        }

        node1=node1.next;

        node2=node2.next;

    }

    return result;

  }

}

算法分析：

1、寻找相交链表的起始节点，首先要判断好什么才意味着相交。

2、相交意味着从某一节点开始直至链表的结束，中间所有的节点都只有一个，也就是说从开始节点开始，两个链表就是一个链表了！

3、那么即使两个链表的长度不同，但两个链表右端一定是对齐的。所以首先我们要获取长度相同的两个链表段，他们的起始点到各自的终点长度一样，这是相交链表的基本要求。

4、所以，我们先获取两个链表各自的长度，接着把根据两个长度的大小关系把各自指针node1、node2指向合适的位置，确保头指针到尾节点的长度一样。

5、接下来，就是判断是否存在占用同一片内存空间的节点了。

6、进行迭代，如找到了这样的节点令result=node1(node2)，并跳出迭代。或者已经迭代到了尾节点，也跳出迭代。否则node1后移一位，node2后移一位。

7、返回节点result，这个节点就是相交节点的入口。

巴特西

LeetCode 160——相交链表（JAVA）

最新文章

热门文章