Intersection of Two Linked Lists : Time Limit Exceeded


  • 0
    H

    Last executed input: Intersected at '1': {1,2,3,4,5,6,7,8,9,10,11,12,13}, {1,2,3,4,5,6,7,8,9,10,11,12,13}

    Why? I think my complexity is O(N). Could anyone help me?Thanks a lot.

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA == null)
            return null;
            if(headB == null)
            return null;
            ListNode lastOfA = getLastNode(headA);
            ListNode lastOfB = getLastNode(headB);
            if(lastOfA != lastOfB)
            return null;
            
            int x = getLength(headA);
            int y = getLength(headB);
            ListNode newHead = inverseList(headA);
            int z = getLength(headB);
            int loc = (y - x + z + 1)/2;
            inverseList(newHead);
            ListNode node = headB; 
            for(int i=0;i<loc-1;i++)
            node = node.next;
            
            return node;
            
        }
        public ListNode getLastNode(ListNode head){
            if(head == null)
            return null;
            if(head.next == null)
            return head;
            ListNode cur = head;
            while(cur.next != null){
                cur = cur.next;
            }
            return cur;
        }
        public int getLength(ListNode head){
            if(head == null)
            return 0;
            int length = 0;
            ListNode cur = head;
            while(cur != null){
                length++;
                cur = cur.next;
            }
            return length;
        }
        public ListNode inverseList(ListNode head){
            if(head == null)
            return null;
            if(getLength(head) == 1)
            return head;
            ListNode pre = null;
            ListNode cur = null;
            ListNode next = null;
            if(getLength(head) == 2){
                pre = head;
                cur = head.next;
                cur.next = pre;
                pre.next = null;
                return cur;
            }
            pre = head;
            cur = head.next;
            while(cur != null){
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    }

  • 0
    H

    I think the reason for your code got "TLE" may be more time cost caused by reverse operation ,even if your code's time complexity is O(N), there are still optimizations you can do.


  • 0
    S

    I feel there are too many while loops. I can see cases where each list is being traversed at least 4 times. I think it should not traverse any list more than twice to keep it under time limit.


  • 0
    H

    thanks. I don't know what is TLE but it is not that reason. I find why my code have a bug in traverse the list. I did not set pre.next =null before last while loop. so there is a circle after this loop. Thus, when you calculate the length of this list, you will got this error.


  • 0
    H

    thank you. But the number of while loops is not the reason.


  • 0
    S

    You are probably right. I would be curious to know the real reason of "Time Limit Exceeded" for your algorithm. It would be very helpful if you can kindly post it when you find it. BTW, here's the reason behind my last comment: Given the example lists that you mentioned, by the time you reach the conclusion that the 1st element is the merge point your algorithm would have traversed ListA 4 times and ListB 2 times in addition to other operations in the algorithm. Where as most of the algorithms that I have seen against this problem would have traversed each list only once. If you consider that then there's a lot of cycle difference.


  • 0
    H

    Yeah ,that 's actually a bug,still I wonder whether you have ACed this problem after your fixing this bug~?


  • 0
    H

    I think your code has some logical problem ~ what if y - x + z + 1 < 0?,and what is the meaning of parameter loc ? Still, every time when you call inverseList(),getLength() and getLastNode(), it will traverse all the link ~ It must have wasted a lot of time~


  • 0
    H

    yeah actually I aced this problem in few minutes after I posted this discussion :) . This bug triggered the "Time Limit Exceeded". Your second question, y - x + z +1 < 0, this case is impossible. It is easy to prove that. Suppose that list A and B have intersection, so the length of A could be represented as X = a + b, and list B is Y = a + c , where a is the length of their intersection. After inversing list A, you would get a new list. The new list C has same head with list B and it's last element is head of List A. So the length of new list is Z = b + c.
    now you have X = a + b; Y = a + c; Z = b + c. Then we could get a, b, c. The problem is solved.


  • 0
    H

    The real reason is mentioned in my first reply to hssyang. Yeah, you are right. In some cases this algorithm could do many unnecessary works. I think the case that List A is actually same with list B is special. What do you think a good method is to check this case ?


Log in to reply
 

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