Accepted java solution, borrow the idea from problem "find the start node of a circular linkedlist"


  • 0
    S

    I borrowed the idea from the problem "find the start node of a circular linkedlist".

    1. Link the last node of A to the head of A. Now the problem change to "Given a linked list (B), detect whether it contains circular part and if so find the start node"
    2. Set two pointer p1=headB(slow) and p2=headB(fast), move p2 two steps each time and p1 one step each time.
    3. If A and B has intersection, p1 and p2 will meet at some time. Then set p1=headB, and move p1 and p2 at same speed (one step each time), they will meet again. That node would be intersection node. Return that node.
    4. If p2 reach the end before they meet, no intersection.
    5. Don't forget to delink A's tail to head before return in either situation. Remember we are not allowed to change the structure of input list.

    ps. I am really confused about how the code formatter works... I tried hundred times before I make it....

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null)
                return null;
            ListNode tail = headA;
            while (tail.next != null) tail = tail.next;
            tail.next = headA;
            ListNode p1 = headB;
            ListNode p2 = headB;
            while(p2.next != null && p2.next.next != null)
            {
                p1=p1.next;
                p2=p2.next.next;
                if (p1 == p2) break;
            }
            if (p2.next == null || p2.next.next == null)
            {
                tail.next = null;
                return null;
            }
            p1 = headB;
            while (p1 != p2)
            {
                p1 = p1.next;
                p2 = p2.next;
            }
            tail.next = null;
            return p1;
        }
    }

Log in to reply
 

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