C++相交链表完整代码
时间: 2023-11-16 12:06:42 浏览: 51
以下是C++相交链表的完整代码,其中包括了两种不同的解法:
解法一:常规遍历方法
```
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 如果单链表A和单链表B至少有一个为空,则两个单链表不存在相交节点,返回null
if(headA == nullptr || headB == nullptr) {
return nullptr;
}
// 记录经过的所有节点
// 注意!这里记录的是单链表的节点,不是节点的值
unordered_set<ListNode *> visited;
// 记录当前节点
ListNode *p=headA;
// 循环遍历单链表A
while(p!=nullptr) {
// 保存访问过的节点
visited.insert(p);
// 访问下一个节点
p=p->next;
}
// 遍历完单链表A后继续遍历单链表B
p=headB;
// 循环遍历单链表B
while(p!=nullptr) {
// 如果当前节点存在于已访问过的节点中
if(visited.count(p)) {
// 则当前节点就是相交节点
return p;
}
// 访问下一个节点
p=p->next;
}
// 两个单链表不存在相交节点,返回null
return nullptr;
}
};
```
解法二:基于双指针的方法
```
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 如果单链表A和单链表B至少有一个为空,则两个单链表不存在相交节点,返回null
if(headA == nullptr || headB == nullptr) {
return nullptr;
}
// 定义两个指针分别指向两个单链表的头节点
ListNode *pA=headA;
ListNode *pB=headB;
// 在两个指针相遇之前,持续遍历两个单链表
while(pA!=pB) {
// 如果单链表A遍历结束
if(pA==nullptr) {
// 将pA指向单链表B的头节点
pA=headB;
} else {
// 否则继续遍历
pA=pA->next;
}
// 如果单链表B遍历结束
if(pB==nullptr) {
// 将pB指向单链表A的头节点
pB=headA;
} else {
// 否则继续遍历
pB=pB->next;
}
}
// 两个指针相遇之后
// 相遇点即为两个单链表的相交节点
return pA;
}
};
```