题目描述
输入两个链表,找出它们的第一个公共节点,如图两个链表从C1开始相交
1、哈希与集合
实现思路:将第一个链表的所有节点存入集合中,遍历第二个链表,并在集合中查询链表二的节点是否出现过
实现代码:
struct ListNode* getInteractionNode_hash(struct ListNode* headA, struct ListNode* headB)
{
set<ListNode*> st;
while (headA != NULL) {
st.insert(headA);
headA = headA->next;
}
while (headB != NULL) {
if (st.count(headB) != 0)return headB;
headB = headB->next;
}
return NULL;
}
2、使用栈
实现思路:根据题意可知在相同节点之后,两链表的节点完全相同,这里我们可以利用栈结构后进先出的特点来实现这一题,分别将两链表存储栈内,同时取出栈顶元素进行对比,当遇到不同节点之后返回上一节点(prev)
实现代码:
struct ListNode* getInteractionNode_stack(struct ListNode* headA, struct ListNode* headB)
{
stack<ListNode*>stkA, stkB;
while (headA != NULL) {
stkA.push(headA);
headA = headA->next;
}
while (headB != NULL) {
stkB.push(headB);
headB = headB->next;
}
ListNode* prevA = NULL, *prevB = NULL;
while (stkA.size() != 0 && stkB.size() != 0) {
ListNode* currA = stkA.top();
stkA.pop();
ListNode* currB = stkB.top();
stkB.pop();
if (currA != currB)break;
prevA = currA;
prevB = currB;
}
return prevA;
}
3、补差法
实现思路:在两链表大小相同时,我们完全可以使用循环的方式逐个判断两链表节点是否相同。所以,遵循这一思路衍生出了两种方法:补差法和拼接法。这里我们先介绍补差法,补差法顾名思义,将两个不同长度的链表的长度差补上。这里的补指的是在循环判断节点相同之前提前移动较长链表的节点,保证后续对比可以同步进行。因为两链表之前的节点全部不相同,所以可以很放心的移动节点。进而完成问题。
实现代码
struct ListNode* getInteractionNode_sub(struct ListNode* headA, struct ListNode* headB)
{
if (headA == NULL || headB == NULL)return NULL;
ListNode *currA = headA, *currB = headB;
int la = 0, lb = 0;
while (currA != NULL) {
++la;
currA = currA->next;
}
while (currB != NULL) {
++lb;
currB = currB->next;
}
int sub = la > lb ? la - lb : lb - la;
currA = headA;
currB = headB;
if (la > lb)
{
int cnt = 0;
while (cnt < sub) {
++cnt;
currA = currA->next;
}
}
if (lb >la) {
int cnt = 0;
while (cnt < sub) {
++cnt;
currB = currB->next;
}
}
while (currA != currB) {
currA = currA->next;
currB = currB->next;
}
return currA;
}
4、双指针法
实现思路:我们为了解决两链表长度不等的问题,衍生出了双指针法(拼接法)。在这里我们可以将理解链表理解成两部分,不同部分(Left)和相同部分(Right)。导致两链表长度不相同的部分为Left部分,这里我们可以利用拼接的方式处理这个问题。
先看下方链表:
A :1 2 3 4 5
B :7 5 4 5
拼接AB与BA
AB :1 2 3 4 5 7 5 4 5
BA :7 5 4 5 1 2 3 4 5
不难发现AB与BA尾部完全相同,这里的尾部就是两链表相同部分(Right)
如果用公式表达出两链表的内容可以得到
AB = Left(A) + Right(A) + Left(B) + Right(B)
BA = Left(B) + Right(B) + Left(A) + Right(A)
根据定义理解Right(A)= Right(B)
Left(A) + Right(A) + Left(B) = Left(B) + Right(B) + Left(A)恒成立
所以对于长度不同的链表可以使用拼接的方法使其总长度相同,进而使其可以比较。
在代码实现方面,我们并不需要直接将两链表拼接,只需要在链表循环至NULL时再从另一个链表开始遍历即可,这里就完成了进一步优化。
代码实现
struct ListNode* getInteractionNode_connect(struct ListNode* headA, struct ListNode* headB)
{
if (headA == NULL || headB == NULL)return NULL;
ListNode *currA = headA, *currB = headB;
while (currA != currB) {
currA = currA->next;
currB = currB->next;
//在拼接后遍历结束时 currA == currB一定成立
//防止两链表完全不同导致死循环 给予null出口
if (currA != currB) {
//两链表长度不同 第一次遍历结束时候
if (currA == NULL) {
currA = headB;
}
if (currB == NULL) {
currB = headA;
}
}
}
return currA;
}
你变成我,走过我走过的路。
我变成你,走过你走过的路。
然后我们便相遇了..
——leetcode
希望对大家能有所帮助。
图片来源:编程导航算法通关村第一期
具体来源:算法通关村第一关——链表—白银挑战文章来源:https://www.toymoban.com/news/detail-640786.html
作者:余秋文章来源地址https://www.toymoban.com/news/detail-640786.html
到了这里,关于算法学习-链表-level2-两个链表的第一个公共节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!