A Java solution with cycle searching

  • 0

    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;
                tailA = tailA.next;
            tailA.next = headB;
            // find cycle
            slow = headA.next;
            fast = headA.next.next;
                if(slow==fast) break;
                slow = slow.next;
                fast = fast.next.next;
            // no cycle
                tailA.next = null;
                return null;
            // get cycle start position
            slow = headA;
                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.