代码随想录-链表相交

题解与说明

要注意区分链表相交是指针相等，而不是值相等。

这里当时没有想清楚，还以为leetcode的样例一给错了，原来人家是想强调这个问题哈哈

这里给出三种解法:(leetcode格式)

① 看了代码随想录的解释后，自己写的代码。

② 看了代码随想录的代码后，对原有的代码循环进行优化。

③在代码随想录学习到的一种精简代码写法。

解法一:

/**
 * 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) {
        //先找到链表的长度距离之差
        int lenA = 0,lenB=0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        while(curB!=null){
            lenB++;
            curB = curB.next;
        }
        int subLen = Math.abs(lenA-lenB);
        curA = headA;
        curB = headB;
        if(lenA>lenB){
            for(int i=0;i<subLen;i++){
                curA = curA.next;
            }
        }else{
            for(int i=0;i<subLen;i++){
                curB = curB.next;
            }
        }
        //A\B两个链表对齐了，一同向后走  寻找第一个相交结点(注意交点的定义是指针相同，而不是数值相同)
        while(curA!=curB){
            curA = curA.next;
            curB = curB.next;
        }
        return curA;

    }
}

解法二:

①简化了移动比较次数，谁长谁是A。②优化了遍历方式，更加的简洁。

/**
 * 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) {
        //先找到链表的长度距离之差
        int lenA = 0,lenB=0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        while(curB!=null){
            lenB++;
            curB = curB.next;
        }
        // int subLen = Math.abs(lenA-lenB);
        curA = headA;
        curB = headB;
       
        // if(lenA>lenB){
        //     for(int i=0;i<subLen;i++){
        //         curA = curA.next;
        //     }
        // }else{
        //     for(int i=0;i<subLen;i++){
        //         curB = curB.next;
        //     }
        // }
         //这里不再比较两次，而是谁长谁是A,交换指针和长度
        if(lenB>lenA){
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        int subLen = lenA - lenB;
        while(subLen-->0){
            curA = curA.next;
        }
        //A\B两个链表对齐了，一同向后走  寻找第一个相交结点(注意交点的定义是指针相同，而不是数值相同)
        while(curA!=curB){
            curA = curA.next;
            curB = curB.next;
        }
        return curA;

    }
}

解法三:双指针

这里对双指针法加一下讲解，如果有不对的欢迎大家指正

双指针法两个指针pA和pB分别在两个链表上，分两种情况

①链表A与B等长，那么只需要循环一次，就能判断是否相交，相交就是交点，不相交就是null

②链表A与B不等长，那其实就是一个大小圈的问题，最后要的是pA与pB对于链表末尾的相对位置一致，最终的效果类似于方法一中的让长的先走几步。

那么这个是怎么解决这个问题的呢，就是遍历两次。假设lenA>lenB,那么A第一次循环跑的是大圈，第二次让它走B的链表，也就是跑小圈，B的指针同理，反着来，主打一个雨露均沾。

两个指针第二圈循环的过程结束，两个指针的移动距离就都是lenA+lenB。

要

/**
 * 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;
        //简单明了，但是相当不好想
        //当不相交的时候，pA和pB两次循环后都会变为null，没问题
        /**当相交时，其实核心思想就是让短的那个链表的指针去跑一下长的那里，让上一次跑长的来跑短的这里，这样两圈下来两个链表的指针总移动位数是一样的
        所以当第二次循环是，如果两个链表有相交的位置，他们就会在第二次循环时候相遇，如果没有，那结束第二次循环后两个都为null，也会停止，太妙了
        核心思想就是先跑长还是先跑短的问题。
        **/
        
        while(pA!=pB){
            pA = pA == null? headB:pA.next;
            pB = pB == null?headA:pB.next;
        }
        return pA;

    }
}

要点总结与心得

1、链表相交比的是指针相等

2、遇到两个长度不等需要讨论的时候，不用讨论，强行让你想代表长的那个成为长的就行了，反正只是个工具

3、双指针太精彩了，数学问题，A+B = B+A;