CShap 两个链表的相交点 源代码
时间: 2024-03-13 12:17:34 浏览: 16
以下是 C# 中找到两个链表的相交点的源代码:
```csharp
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 计算链表 A 和 B 的长度
int lengthA = GetLength(headA);
int lengthB = GetLength(headB);
// 将长度较长的链表先移动多余的部分
if (lengthA > lengthB) {
headA = MoveList(headA, lengthA - lengthB);
} else {
headB = MoveList(headB, lengthB - lengthA);
}
// 同时移动链表 A 和 B,直到它们相遇
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
// 计算链表的长度
private int GetLength(ListNode node) {
int length = 0;
while (node != null) {
node = node.next;
length++;
}
return length;
}
// 将链表移动指定的步数
private ListNode MoveList(ListNode node, int steps) {
while (steps > 0) {
node = node.next;
steps--;
}
return node;
}
}
```
上述解法的时间复杂度为 O(m+n),其中 m 和 n 分别为两个链表的长度,空间复杂度为 O(1)。