LeetCode链表篇【面试题 02.07. 链表相交】

力扣题目链接(opens new window)

给定两个(单向)链表,判定它们是否相交并返回交点。请注意相交的定义基于节点的引用,而不是基于节点的值。换句话说,如果一个链表的第k个节点与另一个链表的第j个节点是同一节点(引用完全相同),则这两个链表相交。

LeetCode链表篇【面试题 02.07. 链表相交】

 

示例 1:

输入:listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]

输出: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 个节点。

正解

1)第一种思路:历遍链表1或2,每次令其历遍元素指向另一个链表的头,并以该元素为起点进行历遍,若size等于另一个链表的长度,那么该元素不为相交点;若陷入循环(size>另一个链表的长度)则证明是交叉点。历遍元素的指针每次要做到复原。[时间复杂度O(n+n*2)]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    
       public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode dummyHeadA = new ListNode(0);
        ListNode dummyHeadB = new ListNode(0);
        dummyHeadA.next = headA;
        dummyHeadB.next = headB;
        ListNode copy=null;
        ListNode ret = null;
        ListNode temp = null;
        int size = 0;
        if (headA != null && headB != null) {
            while (dummyHeadB.next != null) {//获取另一链表的长度
                dummyHeadB = dummyHeadB.next;
                size++;
            }

            while (dummyHeadA.next != null) {
                dummyHeadA = dummyHeadA.next;
                copy=dummyHeadA;//记录当前节点
                if (dummyHeadA.next != null) {//记录下一个节点
                    temp = dummyHeadA.next;
                }else {
                    temp=null;
                }
                dummyHeadA.next = headB;//将HeadA指针移至HeadB
                if (isSame(dummyHeadA, size)) {//如果当前节点符合条件,复原HeadA指针
                    if(temp==null){
                        dummyHeadA.next=null;
                    }else {
                        dummyHeadA.next=temp;
                    }
                    ret = dummyHeadA;
                    break;
                } else {//如果不符合条件,复原指针
                    if (temp!=null){
                        dummyHeadA.next = temp;
                    }else {//若没有下一节点,复原后返回
                        dummyHeadA.next=null;
                        return ret;
                    }
                }
            }
        }

        return ret;
    }
     public static boolean isSame(ListNode a, int size) {
        boolean flag = false;
        int count = 0;
        ListNode temp = a;
        while (temp.next != null) {
            temp = temp.next;
            count++;
            if (count > size) {
                flag = true;
                break;
            }
        }
        return flag;
    }

}

2)第二种思路:不难发现第一种思路的解法很耗时间,通过比较,若两者有交叉点,那么共同部分的长度最多为size=Math.min(sizeA,sizeB);设置两个指针分别指向下标为倒数第size的地方,然后依次比较即可。【时间复杂度:O(3n)】

/**
 * 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 curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头,lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上(末尾位置对齐)
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB,遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
    
}

上一篇:力扣面试题02.07(链表相交)


下一篇:Ultimaker_Cura-4.8-Win版本软件下载与安装