0160.md

160. Intersection of Two Linked Lists

Java Solution(s)

/**
 * 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) {
        int lenA = 0, lenB = 0;
        ListNode dumpHeadA = headA, dumpHeadB = headB;
        while (dumpHeadA != null) {
            dumpHeadA = dumpHeadA.next;
            lenA++;
        }
        while (dumpHeadB != null) {
            dumpHeadB = dumpHeadB.next;
            lenB++;
        }

        dumpHeadA = headA;
        dumpHeadB = headB;
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                dumpHeadB = dumpHeadB.next;
            }
        } else {
            for (int i = 0; i < lenA - lenB; i++) {
                dumpHeadA = dumpHeadA.next;
            }
        }

        while (dumpHeadA != dumpHeadB) {
            dumpHeadA = dumpHeadA.next;
            dumpHeadB = dumpHeadB.next;
        }
        return dumpHeadA;
    }
}

/**
 *这个思路的核心在于pointA和pointB要能为null，如果先pointA = pointA.next，然后判断为null，则需要增加一个flag来避免第二次走到B的起点
 *另一个简单的思路是：先判断为null，再换起点
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pointA = headA, pointB = headB;
        boolean reverseA = true, reverseB = true;
        while (pointA != pointB) {
            pointA = pointA.next;
            if (pointA == null && reverseA) {
                pointA = headB;
                reverseA = false;
            }
            pointB = pointB.next;
            if (pointB == null && reverseB) {
                pointB = headA;
                reverseB = false;
            }
            /**
             * if (pointA == null) {
             *     pointA = headB;
             * } else {
             *     pointA = pointA.next;
             * }
             * if (pointB == null) {
             *     pointB = headA;
             * } else {
             *     pointB = pointB.next;
             * }
             */
        }
        return pointA;
    }
}

Python Solutions

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        pointA: ListNode = headA
        pointB: ListNode = headB
        lenA: int = 0
        lenB: int = 0

        while (pointA is not None):
            lenA += 1
            pointA = pointA.next
        while (pointB is not None):
            lenB += 1
            pointB = pointB.next

        pointA, pointB = headA, headB

        if (lenA < lenB):
            for i in range(lenA, lenB):
                pointB = pointB.next
        else:
            for i in range(lenB, lenA):
                pointA = pointA.next

        while (pointA != pointB):
            pointA = pointA.next
            pointB = pointB.next

        return pointA

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        pointA: ListNode = headA
        pointB: ListNode = headB

        while (pointA != pointB):
            if (pointA is None):
                pointA = headB
            else:
                pointA = pointA.next

            if (pointB is None):
                pointB = headA
            else:
                pointB = pointB.next
        return pointA