首页 > 其他分享 >【链表】LeetCode 160.相交链表

【链表】LeetCode 160.相交链表

时间:2023-01-03 10:02:00浏览次数:64  
标签:p2 p1 ListNode 链表 headB headA 160 LeetCode

题目链接

160. 相交链表

思路1

先测量两个链表的长度,记录差值k=abs(n1 - n2),然后让短的链表先走k步,这样就能保证剩下的长度是一样的,再同步遍历即可。

代码1

class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

    ListNode *p1 = headA;
    ListNode *p2 = headB;
    int n1 = 0;
    int n2 = 0;

    // 分别测算两个链表的长度及其差值
    while(p1){
      p1 = p1->next;
      ++n1;
    }
    while(p2){
      p2 = p2->next;
      ++n2;
    }
    int k = abs(n1 - n2);

    p1 = headA;
    p2 = headB;

    // 总是让p1指向较长的那个链表
    if(n1 < n2){
      swap(p1, p2);
    }

    // 让较长的那个链表先走k步
    while(k--){
      p1 = p1->next;
    }

    // 再同步遍历
    while(p1 && p2){
      if(p1 == p2){
        break;
      }
      p1 = p1->next;
      p2 = p2->next;
    }

    return p1;

  }
};

思路2

根据题目意思 如果两个链表相交,那么相交点之后的长度是相同的

我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此,我们必须消除两个链表的长度差。

  1. 指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
  2. 如果 pa 到了末尾,则 pa = headB 继续遍历;如果 pb 到了末尾,则 pb = headA 继续遍历
  3. 比较长的链表指针指向较短链表head时,长度差就消除了
  4. 如此,只需要将最短链表遍历两次即可找到位置

可以理解成两个人速度一致, 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话,那么这段路上俩人肯定是肩并肩手牵手的。

image

代码2

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA == null || headB == null){
            return headA;
        }

        ListNode pa = headA;
        ListNode pb = headB;

        while(pa != pb){
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }

        return pa;
    }
}

标签:p2,p1,ListNode,链表,headB,headA,160,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17021149.html

相关文章