侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 101 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(11) - 寻找相交链表的相交节点

惊羽
2021-06-22 / 0 评论 / 0 点赞 / 298 阅读 / 648 字
温馨提示:
本文为原创作品,感谢您喜欢~

题目 : 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

结果

image.png

答案

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        int al = 0;
        while(pa != null){
            al++;
            pa = pa.next;
        }

        ListNode pb = headB;

        int bl = 0;
        while(pb != null){
            bl++;
            pb = pb.next;
        }
        int step = 0;
        if(al > bl){
            step = al -bl;
            int s = 0;
            while(headA != null && s < step){
                headA = headA.next;
                s++;
            }
            while (headA != headB){
                headA = headA.next;
                headB = headB.next;
            }
            return headA;

        }else{
            step = bl -al;
            int s = 0;
            while(headB != null && s < step){
                headB = headB.next;
                s++;
            }
            while (headA != headB){
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }
}

思路

将长度比较长的链表指针提前赶到短链表的头结点位置,然后2个指针以同样步伐一步一步往下走,直到找到相交节点或返回空值

0
广告 广告

评论区