My fairly short Java solution :) [Feel free to let me know how I can improve on it!]


  • 1
    W
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            //hashset can be used as an alternative solution here. store headA values and then traverse headB to match.
            if(null == headA || null == headB)
                return null;
            //assumption: linked list is sorted (asc).
            int valA = headA.val;
            int valB = headB.val;
            
            if(valA == valB)
                return headA;
            
            ListNode startWith = valA < valB? headA : headB;
            ListNode oppNode = valA > valB? headA : headB;
            valA = startWith.val;
            valB = oppNode.val;
            
            while(startWith != null){
                valA = startWith.val;
                if(valA == valB){
                    return startWith;
                } else if(valA > valB){
                    if(oppNode.next != null){
                        oppNode = oppNode.next;
                        valB = oppNode.val;
                    } else
                        return null;
                } else if(valA < valB){
                    startWith = startWith.next;
                }
            }
            
            return null;
        }
    }
    

    I believe that this solution runs at O(n) time and uses approximately O(1) space.

    Cheers.


  • 1
    S

    Hello Suan, I am David. Just for a first greet with my solution to this problem, feel free to share your ideas!

        public class Solution {
         public int getLength(ListNode node) {
            int length = 0;
            while (node != null) {
                node = node.next;
                length++;
            }
            
            return length;
        }
        
          public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode nodeA = headA;
            ListNode nodeB = headB;
            int lengthA = getLength(headA);
            int lengthB = getLength(headB);
            int distance = Math.abs(lengthA - lengthB);
            if (lengthA > lengthB) {
                while (distance > 0) {
                    nodeA = nodeA.next;
                    distance--;
                }
            } else {
                while (distance > 0) {
                    nodeB = nodeB.next;
                    distance--;
                }
            }
            
            while (nodeA != null && nodeB != null) {
                if (nodeA == nodeB) return nodeA;
                nodeA = nodeA.next;
                nodeB = nodeB.next;
            }
            
            return null;
        }
       }
    

Log in to reply
 

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