【LeetCode】【算法】160.相交链表
Leetcode 160. 相交链表
题目描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
思路
A+B,一个指针,访问完A访问B;另一个指针,访问完B访问A
若AB相遇则找到相交点,否则无相交点
因为A+B的长度是相等的
代码
/**
* 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 != null || pB != null){
if (pA == pB) return pA;
if (pA == null) {
pA = headB;
} else {
pA = pA.next;
}
if (pB == null) {
pB = headA;
} else {
pB = pB.next;
}
}
return null;
}
}