链表相交两种解法

1.老老实实解

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0,lenB = 0;
        //计算链表A的长度
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        //计算链表B的长度
        while(curB!=null){
            lenB++;
            curB = curB.next;
        }
        //初始化为头节点
        curA = headA;
        curB = headB;
        //无论如何保证链表A的长度最大,不是的话就将两个链表交换
        if(lenB>lenA){
            //交换链表长度
            int temp = lenB;
            lenB = lenA;
            lenA = temp;

            //交换两个链表
            ListNode tmp = curB;
            curB = curA;
            curA = tmp;
        }
        //计算差值
        int gap = lenA - lenB;
        //让他们保持尾部对齐
        while(gap-->0){
            curA = curA.next;
        }
        //两个链表一起向后移找到相同结点
        while(curA!=null){
            if(curA==curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

2.巧解

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA!=curB){
            curA = curA==null?headB:curA.next;
            curB = curB==null?headA:curB.next;
        }
        return curA;//返回curA,curB都行
    }
}

两种方法的执行用时和内存消耗都一样

上一篇:L1-7 等级排序 (20 分)——2022寒假训练测试题目集


下一篇:【每日一题】【链表】2021年11月23日-160. 相交链表