160.相交链表（160相交链表）

## 160. 相交链表### 简介编写一个程序，找到两个单链表相交的起始节点。

示例:

``` 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 ```### 解题思路#### 1. 双指针法

思路:

创建两个指针 pA 和 pB，分别指向链表 A 和链表 B 的头节点。

遍历链表，当指针pA到达链表A的尾节点时，将pA指向链表B的头节点；当指针pB到达链表B的尾节点时，将pB指向链表A的头节点。

继续遍历，直到pA和pB相遇，相遇点即为相交节点。

如果pA和pB遍历完整个链表都没有相遇，则说明两个链表不相交，返回null。

代码实现:

```python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:pA = headApB = headBwhile pA != pB:pA = pA.next if pA else headBpB = pB.next if pB else headAreturn pA ```

复杂度分析:

时间复杂度: O(m+n)，其中 m 和 n 分别为两个链表的长度。

空间复杂度: O(1)。#### 2. 计算长度差

思路:

首先遍历两个链表，计算出它们的长度差 diff。

让较长的链表的指针先移动 diff 步。

然后，两个指针同时向后移动，直到相遇。相遇点即为相交节点。

代码实现:

```python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:lenA = self.getLength(headA)lenB = self.getLength(headB)if lenA > lenB:headA = self.moveHead(headA, lenA - lenB)else:headB = self.moveHead(headB, lenB - lenA)while headA and headB:if headA == headB:return headAheadA = headA.nextheadB = headB.nextreturn Nonedef getLength(self, head):length = 0while head:length += 1head = head.nextreturn lengthdef moveHead(self, head, steps):while steps > 0:head = head.nextsteps -= 1return head ```

复杂度分析:

时间复杂度: O(m+n)，其中 m 和 n 分别为两个链表的长度。

空间复杂度: O(1)。### 总结双指针法和计算长度差法都是解决“相交链表”问题的有效方法。双指针法代码简洁，而计算长度差法更容易理解。

160. 相交链表

简介编写一个程序，找到两个单链表相交的起始节点。**示例:**``` 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 ```

解题思路

1. 双指针法**思路:*** 创建两个指针 pA 和 pB，分别指向链表 A 和链表 B 的头节点。 * 遍历链表，当指针pA到达链表A的尾节点时，将pA指向链表B的头节点；当指针pB到达链表B的尾节点时，将pB指向链表A的头节点。 * 继续遍历，直到pA和pB相遇，相遇点即为相交节点。 * 如果pA和pB遍历完整个链表都没有相遇，则说明两个链表不相交，返回null。**代码实现:**```python

Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:pA = headApB = headBwhile pA != pB:pA = pA.next if pA else headBpB = pB.next if pB else headAreturn pA ```**复杂度分析:*** 时间复杂度: O(m+n)，其中 m 和 n 分别为两个链表的长度。 * 空间复杂度: O(1)。

2. 计算长度差**思路:*** 首先遍历两个链表，计算出它们的长度差 diff。 * 让较长的链表的指针先移动 diff 步。 * 然后，两个指针同时向后移动，直到相遇。相遇点即为相交节点。**代码实现:**```python

Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:lenA = self.getLength(headA)lenB = self.getLength(headB)if lenA > lenB:headA = self.moveHead(headA, lenA - lenB)else:headB = self.moveHead(headB, lenB - lenA)while headA and headB:if headA == headB:return headAheadA = headA.nextheadB = headB.nextreturn Nonedef getLength(self, head):length = 0while head:length += 1head = head.nextreturn lengthdef moveHead(self, head, steps):while steps > 0:head = head.nextsteps -= 1return head ```**复杂度分析:*** 时间复杂度: O(m+n)，其中 m 和 n 分别为两个链表的长度。 * 空间复杂度: O(1)。

总结双指针法和计算长度差法都是解决“相交链表”问题的有效方法。双指针法代码简洁，而计算长度差法更容易理解。