相交链表

作者: 小白学编程 | 来源:发表于2018-09-23 21:31 被阅读2次

    编写一个程序,找到两个单链表相交的起始节点。

    注意:

    如果两个链表没有交点,返回 null.
    在返回结果后,两个链表仍须保持原有的结构。
    可假定整个链表结构中没有循环。
    程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

    思路

    两条链表长度相减,得到长度之差count,再让长的链表走count步,然后两条链表同时走,即可得到相交的节点

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode a=headA;
            ListNode b=headB;
            int lenA=0,lenB=0;
            while(a!=null){
                a=a.next;
                lenA++;
            }
            
            while(b!=null){
                b=b.next;
                lenB++;
            }
            
            int count=0;
            if(lenA>=lenB){
                count=lenA-lenB;
                for(int i=0;i<count;++i){
                    headA=headA.next;
                }
            }else{
                count=lenB-lenA;
                for(int i=0;i<count;++i){
                    headB=headB.next;
                }
            }
            
            while(headA!=headB){
                headA=headA.next;
                headB=headB.next;
            }
            
            return headA;
        }
    }
    

    相关文章

      网友评论

        本文标题:相交链表

        本文链接:https://www.haomeiwen.com/subject/wybqoftx.html