Python solution for intersection of two singly linked lists


  • 26
    P
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param two ListNodes
        # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            curA,curB = headA,headB
            lenA,lenB = 0,0
            while curA is not None:
                lenA += 1
                curA = curA.next
            while curB is not None:
                lenB += 1
                curB = curB.next
            curA,curB = headA,headB
            if lenA > lenB:
                for i in range(lenA-lenB):
                    curA = curA.next
            elif lenB > lenA:
                for i in range(lenB-lenA):
                    curB = curB.next
            while curB != curA:
                curB = curB.next
                curA = curA.next
            return curA
    

    The solution is straightforward: maintaining two pointers in the lists under the constraint that both lists have the same number of nodes starting from the pointers. We need to calculate the length of each list though. So O(N) for time and O(1) for space.


  • 0
    S

    Very clear code! I like it!

    I used to code in Java, not very familiar with Python grammar but had the same algorithm as you did, thanks for implementing it out.


  • 0
    K

    Well Done! It seems that Python show a more succinct code than C++(I used to it). No pointer in Python makes it more happy.:-)


  • 0
    L

    good implement


  • 0
    S

    Good job! I could easily follow your thought! Thanks a lot!


  • 0
    G

    you are so smart.


  • 0
    Y

    What if there is no intersection found? Shouldn't we compare the tails of the linkedlist and return False if tails are not the same?


  • 0

    Now it got MLE.


  • 0
    L

    @jedihy that's right~


  • 4
    J

    @jedihy said in Python solution for intersection of two singly linked lists:

    Now it got MLE.

    MLE can be solved by "import gc" and adding "gc.collect()" before "curA,curB = headA,headB"


  • 0
    S

    @peaceful Your code cannot pass the test. My code is similar with yours, which cannot pass. Then I copied your code to run and it also cannot pass. It gives memory limit exceed error.


  • 0
    M

    Here is the implementation in C.

    struct ListNode *getIntersectionNode(struct ListNode *headA,
                                         struct ListNode *headB)
    {
        struct ListNode *node1 = headA, *node2 = headB;
        int lenA = 0, lenB = 0;
    
        /* Find the length of the lists */
        while (node1 || node2){
            if (node1) {
                node1 = node1->next;
                lenA++;
            }
            if (node2) {
                node2 = node2->next;
                lenB++;
            }
        }
    
        /* Move the first or second list pointer based on the difference */
        node1 = headA;
        node2 = headB;
        /* Scan forward to cover the difference in length */
        while (lenA > lenB) {
            node1 = node1->next;
            --lenA;
        }
        while (lenB > lenA) {
            node2 = node2->next;
            --lenB;
        }
    
        /* Now scan both the lists together to find the intersection */
        while (node1 != node2 && node1 && node2) {
            node1 = node1->next;
            node2 = node2->next;
        }
    
        /* Return the intersection */
        return node1;
    }
    

  • 0
    O

    @songgaoxian Yeah, same question. This is a weird situation.


  • 0
    L

    @onerhao Yes, same problem, it should pass the test.


Log in to reply
 

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