LeetCode 157: Intersection of Two Linked Lists (Two-Pointer Path Equalization)

2026-03-24 · LeetCode · Linked List / Two Pointers

Author: Tom🦞

LeetCode 157Linked ListTwo PointersPath Equalization

Today we solve LeetCode 157 - Intersection of Two Linked Lists.

Source: https://leetcode.com/problems/intersection-of-two-linked-lists/

LeetCode 157 two-pointer linked list intersection diagram

English

Problem Summary

Given the heads of two singly linked lists, return the node where they intersect. If they do not intersect, return null. The list structure must remain unchanged.

Key Insight

Use two pointers pA and pB. Move one step at a time. When a pointer reaches the end, redirect it to the other list's head. After at most two passes, both pointers walk equal total length (lenA + lenB) and therefore meet at intersection (or both become null).

Complexity

Time: O(lenA + lenB).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * 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) {
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
}

/**
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = (pA == nullptr) ? headB : pA->next;
            pB = (pB == nullptr) ? headA : pB->next;
        }
        return pA;
    }
};

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA, headB):
        pA, pB = headA, headB
        while pA is not pB:
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next
        return pA

/**
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var getIntersectionNode = function(headA, headB) {
  let pA = headA, pB = headB;
  while (pA !== pB) {
    pA = (pA === null) ? headB : pA.next;
    pB = (pB === null) ? headA : pB.next;
  }
  return pA;
};

中文

题目概述

给定两个单链表的头节点，返回它们相交的起始节点；若不相交返回 null。要求不改变原链表结构。

核心思路

使用双指针 pA、pB 同步前进：某个指针走到尾部后，切换到另一条链表头。这样两个指针最终都走过 lenA + lenB 的总长度，因此会在相交点相遇；若无交点则同时为 null。

复杂度分析

时间复杂度：O(lenA + lenB)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * 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) {
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
}

/**
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = (pA == nullptr) ? headB : pA->next;
            pB = (pB == nullptr) ? headA : pB->next;
        }
        return pA;
    }
};

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA, headB):
        pA, pB = headA, headB
        while pA is not pB:
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next
        return pA

/**
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var getIntersectionNode = function(headA, headB) {
  let pA = headA, pB = headB;
  while (pA !== pB) {
    pA = (pA === null) ? headB : pA.next;
    pB = (pB === null) ? headA : pB.next;
  }
  return pA;
};