当前位置: 代码迷 >> 综合 >> leetcode160. Intersection of Two Linked Lists(寻找两个链表的交叉点)
  详细解决方案

leetcode160. Intersection of Two Linked Lists(寻找两个链表的交叉点)

热度:54   发布时间:2023-11-17 01:23:37.0

题目要求 (技巧题)

写一个程序来实现,自动寻找两个链表的交叉点。如图:
交叉点是c1
A,B两个链表的交叉点是c1

示例演示

在这里插入图片描述

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: 输入的交叉点的值是8(注意如果两个链表交叉,那么这个值一定不能为0) 
从A的头开始读取,A是[4,1,8,4,5]. 
从B的头开始读取,B是[5,0,1,8,4,5]. 
A中在交叉点之前有两个结点,B中在交叉点之前有三个结点。

在这里插入图片描述

IInput: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: 输入的交叉点的值是2(注意如果两个链表交叉,那么这个值一定不能为0) 
从A的头开始读取,A是[0,9,1,2,4]. 
从B的头开始读取,B是[3,2,4]. 
A中在交叉点之前有三个结点,B中在交叉点之前有一个结点。

在这里插入图片描述

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: 
从A的头开始读取,A是[2,6,4]. 
从B的头开始读取,B是[1,5]. 由于两个列表没有交叉,所以交点必须为0.
Explanation: 
两个表没有交叉,所以返回空。

解题思路

通过上面实例给出的情况,我们把操作分成三种类型,第一种是有交点且A比B长,第二种是有交点且A比B短,第三种是A,B没有交点。

接着一个问题,如何去判断有无交点?
注意:这个交点是指定的,不是有相同的元素值就可以(比如ex1中的1),我们可以理解为当两个链表指向同一个元素时即为相交 根据这种思路,我们想到可以使用指针相等来判断,分别遍历两个链表,当两个指针相等时侯(即指向同一个位置或者同时为空)那么就能证明两个链表相交(不相交)。

下一个问题,链表不等长怎么遍历判断?
这里有一个小技巧,组合A,B两个链表的长度。
当A遍历完成后,指向B的表头继续遍历。
当B遍历完成后,指向A的表头继续遍历。
这样的话,A,B两个链表在长度上就为“一致”了。

主要代码c++

/*** 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) {
    ListNode *p1 = headA;ListNode *p2 = headB;while(p1 != p2) //两种情况指针相等,一个是交点(指向同一个点地址相同),另一种是没有交点全都指向末尾的空指针{
    p1 = p1? p1->next: headB; //遍历链表,若A到尾则移到B的头部p2 = p2? p2->next: headA; //遍历链表,若B到尾则移到A的头部}return p1; //返回交点或者空}
};

原题链接:https://leetcode.com/problems/intersection-of-two-linked-lists/

  相关解决方案