个人技术分享

题目

• 原题连接：160. 相交链表

1- 思路

• 模式识别：相交链表 ——> 判断是否相交

思路

• 保证 headA 是最长的那个链表，之后对其开始依次遍历

2- 实现

⭐160. 相交链表——题解思路

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 求 headA 和 headB 长度
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        while(curB!=null){
            lenB++;
            curB = curB.next;
        }
        if(lenB>lenA){
            ListNode tmp = headB;
            headB = headA;
            headA = tmp;

            int lenTmp = lenA;
            lenA = lenB;
            lenB = lenTmp;
        }
        curA = headA;
        curB = headB;
        for(int i = 0 ; i < lenA-lenB ;i++){
            curA = curA.next;
        }

        while(curA!=null  && curB!=null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

3- ACM 实现

public class intersectLink {

    static class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int x){
            val =x;
        }
    }


    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 求 headA 和 headB 长度
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        while(curB!=null){
            lenB++;
            curB = curB.next;
        }
        if(lenB>lenA){
            ListNode tmp = headB;
            headB = headA;
            headA = tmp;

            int lenTmp = lenA;
            lenA = lenB;
            lenB = lenTmp;
        }
        curA = headA;
        curB = headB;
        for(int i = 0 ; i < lenA-lenB ;i++){
            curA = curA.next;
        }

        while(curA!=null  && curB!=null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入链表A和B的长度");
        int lenA = sc.nextInt();
        int lenB = sc.nextInt();
        System.out.println("输入链表A元素");
        ListNode headA = new ListNode(-1);
        ListNode curA = headA;
        for(int i = 0 ; i < lenA; i++){
            curA.next = new ListNode(sc.nextInt());
            curA = curA.next;
        }

        System.out.println("输入链表B的元素");
        ListNode headB = new ListNode(-1);
        ListNode curB = headB;
        for(int i = 0 ; i < lenB;i++){
            curB.next = new ListNode(sc.nextInt());
            curB = curB.next;
        }

        System.out.println("输入相交链表的长度");
        int intersectLen = sc.nextInt();
        ListNode intersectHead = new ListNode(-1);
        ListNode curIntersect = intersectHead;
        System.out.println("输入相交链表");
        for(int i = 0 ; i < intersectLen;i++){
            curIntersect.next = new ListNode(sc.nextInt());
            curIntersect = curIntersect.next;
        }

        if (intersectLen > 0) {
            curA.next = intersectHead.next;
            curB.next = intersectHead.next;
        }

        ListNode forRes = getIntersectionNode(headA,headB);
        System.out.println(forRes.val);
    }

}