寻找链表相交节点的高效算法-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134842814

本文介绍了两种方法解决链表相交节点问题：法1使用冗余计数器检查，法2采用循环比较直至找到共同节点。法2被推荐为更简洁的最优解法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Python

# 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]:
        cur1, cur2 = headA, headB
        while cur1 != cur2: # 注意: None是可以比较的, 且None = None
            cur1 = cur1.next if cur1 != None else headB
            cur2 = cur2.next if cur2 != None else headA
        
        return cur1

Java

法1:写法不简练

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA, curB = headB;
        int aMeetNull = 0;
        while (aMeetNull < 2) {
            if (curA == curB) {
                return curA;
            }
            if (curA.next != null) {
                curA = curA.next;
            } else {
                ++aMeetNull;
                curA = headB;
            }
            if (curB.next != null) {
                curB = curB.next;
            } else {
                curB = headA;
            }
        }
        return null;
    }
}

法2:最佳写法

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        while (curA != curB) {
            curA = curA != null ? curA.next : headB;
            curB = curB != null ? curB.next : headA;
        }
        return curA;
    }
}