相交链表求节点是一个常见的链表问题，涉及到判断两个链表是否相交以及找到相交部分的节点。本文将从链表的常见问题、判定相交链表、求解相交节点三个方面进行详细阐述。
一、链表的常见问题
链表是一种常见的数据结构，其主要特点是通过指针相连的节点的集合。在链表的操作中，常见的操作包括：插入节点、删除节点、查找节点等。其中，判断链表是否相交是一个重要的问题。
二、判定相交链表
判断两个链表是否相交的常见方法是先遍历两个链表，分别得到它们的长度l1和l2，然后让较长的链表先走|l1-l2|步，使得两个链表起点对齐，最后同时遍历两个链表，找到第一个相同的节点即为相交节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode *p1 = headA, *p2 = headB;
while (p1 != NULL) {
lenA++;
p1 = p1->next;
}
while (p2 != NULL) {
lenB++;
p2 = p2->next;
}
p1 = headA;
p2 = headB;
int diff = abs(lenA - lenB);
if (lenA > lenB) {
for (int i = 0; i < diff; i++) {
p1 = p1->next;
}
} else {
for (int i = 0; i < diff; i++) {
p2 = p2->next;
}
}
while (p1 != NULL && p2 != NULL) {
if (p1 == p2) {
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return NULL;
}
};
三、求解相交节点
找到相交节点后，可以使用双指针法遍历两个链表，直到找到相同节点即为相交节点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode *p1 = headA, *p2 = headB;
while (p1 != NULL) {
lenA++;
p1 = p1->next;
}
while (p2 != NULL) {
lenB++;
p2 = p2->next;
}
p1 = headA;
p2 = headB;
int diff = abs(lenA - lenB);
if (lenA > lenB) {
for (int i = 0; i < diff; i++) {
p1 = p1->next;
}
} else {
for (int i = 0; i < diff; i++) {
p2 = p2->next;
}
}
while (p1 != NULL && p2 != NULL) {
if (p1 == p2) {
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return NULL;
}
};
四、总结
本文从链表的常见问题、判定相交链表、求解相交节点三个方面对相交链表求节点问题进行了详细阐述。希望能对读者有所帮助。
原创文章，作者：WPSTD，如若转载，请注明出处：https://www.506064.com/n/373866.html
微信扫一扫 
支付宝扫一扫 