题目描述
题目分析
目标是找到两个链表若相交时的公共结点,那么便需要分析公共结点所具有的特性。
假设链表A和链表B具有公共结点,那么在公共结点处之后,两个链表具有相同长度和数值的结点。而在公共结点之前,两个链表的所具有的结点个数并不一定相等。
因此,若分别从链表A和B的公共结点开始遍历直到遍历到NULL结束,则链表A和链表B的遍历次数一定相等。问题的关键便是如何找到这一部分相等的长度,影响我们无法找到长度的因素是链表A和B公共节点之前的链表,因为公共结点之前的链表长度不一定相等。
因此,我们从链表的长度进行研究。
设链表A的长度为:
a + x = la
其中a为公共结点之前的链表长度,x为从公共结点到最后一个结点的长度,la为链表A的总长度。
设链表B的长度为:
b + x = lb
其中b为公共结点之前的链表长度,x为从公共结点到最后一个结点的长度,lb为链表B的总长度。
而我们可发现a + b + x = la + b = lb + a,根据这一条件,便可以找到等价关系,便找到了边界条件。
所以,la + b = lb + a,即走完A后再走B的前一段距离等于走完B后再走A的前一段距离。
参考文章:
图解相交链表
Intersection of Two Linked Lists (双指针,链表拼接)
代码实现
分别定义一个指针cur_a指向headA和指针cur_b指向headB,当cur_a遍历完headA时,让它指向headB的开头,同理,让cur_b遍历完时,让它指向headA的开头。目的是让两个指针分别走过上述a + b + x
长度的路程,从而消除两个链表之间的长度差。当消除完后,两个链表的下一个结点,便是公共结点。
当走完后,如果为NULL,则说明无公共结点,否则返回的便是公共结点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
if(headA == nullptr && headB == nullptr)
return nullptr;
ListNode* cur_a = headA;
ListNode* cur_b = headB;
while(cur_a != cur_b) {
cur_a = (cur_a ? cur_a->next : headB);
cur_b = (cur_b ? cur_b->next : headA);
}
return cur_a;
}
};
# 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) -> ListNode:
p1, p2 = headA, headB
while p1 != p2 :
p1 = p1.next if p1 else headB
p2 = p2.next if p2 else headA
return p1
时间复杂度为O(n),空间复杂度为O(n)
链表相交