链表05-链表相交

Posted on Edited on

​ 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

图示两个链表在节点 c1 开始相交**：**

链表相交

这个题目有很多种思路 不过labuladong的思路我感觉是最简短和易懂的

把链表A和链表B单独抽离出来后，抓住相交后半段链表长度一定相同的特点，分别遍历链表A和链表B，走完一遍后接上对方的链表，继续遍历直到找到相同的节点

labuladong

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        cur1=headA
        cur2=headB
        while cur1!=cur2:
            if cur1:
                cur1=cur1.next
            else :
                cur1=headB
            if cur2:
                cur2=cur2.next
            else :
                cur2=headA
                
      """
      	 有一点需要提醒一下就是当遍历完A链表后 其实指针不是立刻接上B链表的  是会存在NULL的一刻
      	 a1->a2->None->b1->b2->b3->None
      	 b1->b2->b3->None->a1->a2->None
      	 
      """