160. 相交链表(Intersection of Two Linked Lists) - 《leetcode》

来源
描述
题解

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

描述

编写一个程序，找到两个单链表相交的起始节点。

注意：

如果两个链表没有交点，返回 null
在返回结果后，两个链表仍须保持原有的结构
可假定整个链表结构中没有循环

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存

题解

A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点；如果A,B不相交的话两个指针就会同时到达A+B（B+A）的尾节点

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if (headA == null || headB == null) return null;
      ListNode curA = headA, curB = headB;
      // will stop after second iteration if no intersection exists
      while (curA != curB) {
          curA = (curA == null) ? headB : curA.next;
          curB = (curB == null) ? headA : curB.next;
      }
      return curA;
  }
}

复杂度分析

时间复杂度：
空间复杂度：