提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

两个链表的第一个公共节点（剑指offer 52）Java双指针

2023-03-14 22:54:26 时间

一、题目描述


输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

ee7f51cdd87c429895c258993a848ee9.png



在节点 c1 开始相交。

示例 1：

a161216d7d924597b0f97f73df0d5808.png

输入：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：3ada828a15904e9cbc9b5dedc3553e61.png


输入：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：

fd0ce058201e44338ec935f8ddaf3e73.png


输入：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) 内存。


二、思路讲解

       

最简单的方法是想到HashSet。将一个链表A的节点全部放入集合中，然后遍历另一个链表B，若B中某个节点存在于集合中，说明后面的结构是A、B共同的子结构。


三、Java代码实现 


/**
 * 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) {
        ListNode temp = headA;
        Set<ListNode> set = new HashSet<>();
        while(temp != null){
            set.add(temp);
            temp = temp.next;
        }
 
        temp = headB;
        while(temp!=null){
            if(set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}


四、时空复杂度分析 

       

时间复杂度：        O(M+N)        需要遍历两个链表

       

空间复杂度：        O(N)             需要存储一个链表


五、代码优化 


1、使用双指针 空间复杂度降为O(1)

       

由于两个链表不一样长，那么我们用两个指针分别指向链表的头，较长的那个指针先走，等走到一样长的位置时，再一起走，如果两个指针所指的节点相同，就返回。


如果没有公共部分，也成立，这种情况下走到链表最后的null的时候，返回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) {
        ListNode pa = headA;
        ListNode pb = headB;
        int len_a = 0;  //链表A长度
        int len_b = 0;  //链表B长度
        //计算链表A长度
        while(pa != null){
            len_a++;
            pa = pa.next;
        }
        //计算链表B长度
        while(pb != null){
            len_b++;
            pb = pb.next;
        }
 
        pa = headA;
        pb = headB;
        //长的先跑
        if(len_a > len_b){
            for(int i=0; i<len_a - len_b; i++){
                pa = pa.next;
            }
        } else {
            for(int i=0; i<len_b - len_a; i++){
                pb = pb.next;
            }
        }
 
        //一起跑
        while(pa != pb){
            pa = pa.next;
            pb = pb.next;
        }
        return pa;
    }
}


2、更优雅的双指针 

       

还是让两个指针分别指向两个链表，假设指针pa指向headA，指针pb指向headB。当pa遍历玩A链表之后，去遍历B链表；当pb遍历完B链表之后，去遍历A链表。当两指针相遇时，即为公共部分的第一个节点。

       

如何证明？


假设A链表长度为a，B链表长度为b，公共部分长度为c。那么，pa遍历完A链表，走的长度为a，此时它去遍历B链表，走到公共节点处，一共需走a+(b-c)；pb遍历完B链表，走的长度为b，此时它去遍历A链表，走到公共节点处，一共需走b+(a-c)。两个指针所走的长度恰好相等。所以，当两指针第一次相遇，所处的节点即是所求。

再看看如果没有公共节点，是否成立。

        

没有公共节点，则c=0。表示pa遍历完A,B；pb遍历完B,A，最后都为null，此时跳出循环，返回null。成立。 


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = (A!=null) ? A.next : headB;
            B = (B!=null) ? B.next : headA;
        }
        return A;
    }
}


相关文章