C# O(n) runtime O(1) space


  • 1
    K
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            if (headA == null || headB == null)
                return null;
            
            ListNode currA = headA;
            ListNode currB = headB;
    
            while (currA != currB){
                currA = currA == null ? headB : currA.next;
                currB = currB == null ? headA : currB.next;
            }
            
            return currA;
        }
    }

  • 0
    Z

    @Kanac I don't think this is O(n) runtime, the total number of runs will be the lowest common multiple of the length of the 2 lists which lead the run time to O(n2)


  • 0
    K

    @ZhongzhiZhang

    Why would it be the lowest common multiple of the length of the 2 lists? After they both swap to each other's head, both lists will be aligned. Then there's 2 cases: Intersection or no intersection. For intersection, they will meet somewhere on the iteration after they both swap. Otherwise, for no intersection, they will meet at the null node. This is still a linear operation.


Log in to reply
 

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