A Java solution with cycle searching


  • 0
    J

    It is accepted by OJ. But will appending lists violate the requirement of no modification to list structure?

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // append a list to another
            // if there is an intersection, there will be a cycle in the new list
            // use two pointers to find the position where the cycle starts
            if(headA==null||headB==null) return null;
            if(headA==headB) return headA;
            ListNode slow, fast, tailA;
            // find the tail nodes of list A, and append B
            tailA = headA;
            while(tailA.next!=null){
                tailA = tailA.next;
            }
            tailA.next = headB;
            // find cycle
            slow = headA.next;
            fast = headA.next.next;
            while(fast!=null&&fast.next!=null){
                if(slow==fast) break;
                slow = slow.next;
                fast = fast.next.next;
            }
            // no cycle
            if(fast==null||fast.next==null){
                tailA.next = null;
                return null;
            }
            // get cycle start position
            slow = headA;
            while(slow!=fast){
                slow = slow.next;
                fast = fast.next;
            }
            tailA.next = null;
            return fast;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.