算法——链表相交（leetcode23）

链表相交这题就是找出两个相交链表相交的节点并返回

如上图假设上方第一个节点是链表A的头结点下方第一个节点是链表B的头结点

解法有以下两种

方法一(移动长链表指针后同步移动两个链表的指针直至相等)

也就是先遍历链表A和链表B的长度接着得到链表A和B长度的差值然后领长链表的指针指向差值后个节点此时链表A的指针与链表B的指针就同步了接着同步移动链表A指针p1和链表B指针p2即可直到p1==p2即找到相交节点返回即可

/**
 * 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;
        int lenB = 0;
        // 计算出链表A、B的长度
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        if (lenB > lenA) {
            curA = headB;
            curB = headA;
        }else{
        curA = headA;
        curB = headB;}
        int sub=Math.abs(lenA-lenB);
        for(int i=0;i<sub;i++){
            curA=curA.next;
        }
        while(curA!=null){
            if(curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}

方法二(同步移动指针)

同步移动指针即设指针p1指向链表A头结点指针p2指向链表B头结点,当p1!=p2且p1或p2！=null的时候p1、p2同时向后一个节点移动 如果p1等于null那么令p1指向链表B头结点接着同向移动即可,p2等于null时令p2指向链表A头结点，这样的话p1和p2在相交节点相遇之前走过的节点个数是相同的只要相交 p1必然会等于p2

/**
 * 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 p1=headA;
        ListNode p2=headB;
        while(p1!=p2){
            if(p1==null)p1=headB;
            else p1=p1.next;
            if(p2==null)p2=headA;
            else p2=p2.next;
        }
        return p1;
    }
}

总结:

第一种方法是最容易想出来的但代码量较高第二种方法代码较为简洁但初次接触会难以理解需配合画图来帮助理解,另外一定要首先读懂题意再做题,我刚开始做这道题还以为是找两个链表值相等的节点并返回导致一直解不出题将自己陷进去了，后来才明白题目的意思是要找相交节点也就是两个链表相交在一起的节点，总之做题前要先读懂题意！

原文地址：https://blog.csdn.net/Lemon_man_/article/details/143858024

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！