leetcode106.相交链表

问题描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

题目链接：相交链表

示例

提示

  listA 中节点数目为 m
  listB 中节点数目为 n
  1 <= m, n <= 3 * 104
  1 <= Node.val <= 105
  0 <= skipA <= m
  0 <= skipB <= n
  如果 listA 和 listB 没有交点，intersectVal 为 0
  如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

具体思路

思路一

  遍历listA链表，将listA链表中的每个值与listB链表中每个节点的值进行比较，比较节点地址相等的话就是交点。但是这种方法的时间复杂度比较高是O（$N^2$）

思路二

  先分别找listA链表和listB链表的尾，如果尾节点相等，那么就是相交链表，不是就直接返回NULL，然后分别计算链表的长度，让长的链表先走他们的长度差值步，然后再同时走，如果走到节点的地址是一样的话，那么就是相交的节点

代码实现

//思路2
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA;
    struct ListNode* tailB=headB;
	int lenA=1,lenB=1;
    while(tailA->next)
    {
        tailA=tailA->next;
        lenA++;
    }

    while(tailB->next)
    {
        tailB=tailB->next;
        lenB++;
    }

    if(tailA!=tailB)
    {
         return NULL;
    }
   
    int gap =abs(lenA-lenB);
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }

    while(gap--)
    {
        longlist=longlist->next;
    }

    while(longlist!=shortlist)
    {
         longlist=longlist->next;
         shortlist=shortlist->next;
    }
    
    return longlist;
}