相交链表

题目

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

例如，下面的两个链表：

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

首先要判断两个链表是否相交：是否有相同的尾节点
将问题转换为求链表环的入口节点：将尾节点指向链表B的头结点
环的长度即为链表b的长度，可在遍历时记录，设为n
两个指针一个先走n步，再一块走，当它们相遇时就指向的入口节点，即为所求交点
最后，别忘了把尾指针的next指向null

代码

import java.util.Scanner;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);

        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);

        ListNode headB = new ListNode(7);
        headB.next = new ListNode(8);
        headB.next.next = new ListNode(9);
        // headB.next.next.next = headA.next.next.next;

        ListNode p = solution.getIntersectionNode(headA,headB);

        if(p != null)
            System.out.println(p.val);
        else
            System.out.println("null");
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
 
        //首先要判断两个链表是否相交：是否有相同的尾节点
        ListNode pA = headA;
        while(pA.next != null) 
         pA = pA.next;

        ListNode pB = headB;
        int countB = 1;
        while(pB.next != null) {
            pB = pB.next;
            countB++;
        }

        if(pA != pB) return null;
        
        //将尾节点指向链表B的头结点
        pB.next = headB;
        
        //两个指针一个先走n步，再一块走，当它们相遇时就指向的入口节点，即为所求交点
        ListNode p1 = headA,p2 = headA;
        
        while(countB > 0) {
            p1 = p1.next;
            countB--;
        }
        while(p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        pB.next = null;

        return p1;
    }
}