本文共 1596 字，大约阅读时间需要 5 分钟。

题目描述

编写一个程序，找到两个单链表相交的起始节点。注意：如果两个链表没有交点，返回 null.在返回结果后，两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

普通版

分别计算两个链表的长度

长的先走n-m步

两个个一起走，就能得到公共节点

普通版代码

public class Solution {
       public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
           if ((headA==null)||(headB==null)) return null;                int num1=0;        ListNode p=headA;        while(p!=null){
               num1++;            p=p.next;        }        int num2=0;        ListNode q=headB;        while(q!=null){
               num2++;            q=q.next;        }        if (num1>num2){
               int count=num1-num2;            while(count!=0){
                   headA=headA.next;                count--;            }        }else if (num1

高级版

两个链表同时走

第一个链表如果走到头，就从第二个链表开始走

第二个链表如果走到头，就从第一个链表开始走

和普通版原理一样，相当于长链表先走了n-m步

高级版代码

public class Solution {
       public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
           if ((headA==null)||(headB==null)) return null;        ListNode p = headA;        ListNode q = headB;        int flag=0;        while(true){
               if (p==null){
                   if (flag==2) return null;                p=headB;                flag++;            }            if (q==null){
                   if (flag==2) return null;                q=headA;                flag++;            }            if (p==q){
                   return p;            }            p=p.next;            q=q.next;        }    }}