# 34. 相交链表

java

```java
// 链表工具类
public class LinkedUtils {
    public static ListNode arrayToLinkedList(int[] array){
        if(array==null) return null;
        //head node 
        ListNode root=new ListNode(-1);
        ListNode p=root;

        int size=array.length;
        int i=0;
        while(i<size){
            ListNode q=new ListNode(array[i++]);
            q.next=null;
            p.next=q;
            p=q;
        }

        return root.next;
    }

    public static void print(ListNode root) {
        if(root==null) System.out.println("root is null");
        else{
            while(root!=null){
                System.out.print(root.val);
                if(root.next!=null){
                    System.out.print("->");
                }
                root=root.next;
            }
            System.out.println();
        }
    }

    public static int length(ListNode root) {
        if(root==null) return 0;
        int n=0;
        while(root!=null){
            root=root.next;
            n++;
        }
        return n;
    }

    // 返回指向链表尾部的指针
    public static ListNode moveToTail(ListNode root) {
        if(root==null) return null;
        ListNode tail=root;
        while(tail.next!=null){
            tail=tail.next;
        }
        return tail;
    }
}


// 定义链表
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val=val;
    }
}



/**
 * 160. 相交链表
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 *
 *
 * 例如，下面的两个链表：
 *
 * A:          a1 → a2
 *                    ↘
 *                      c1 → c2 → c3
 *                    ↗
 * B:     b1 → b2 → b3
 * 在节点 c1 开始相交。
 *
 *
 *
 * 注意：
 *
 * 如果两个链表没有交点，返回 null.
 * 在返回结果后，两个链表仍须保持原有的结构。
 * 可假定整个链表结构中没有循环。
 * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 *
 */
public class Solution160 {

    /**
     * 求出两个链表的长度m,n，长链表的指针先走|n-m|，然后再同步走
     * 两个链表相交，那么相交部分的长度是相同的
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        int lenA=length(headA);
        int lenB=length(headB);
        ListNode nodeA=headA;
        ListNode nodeB=headB;
        int k=0;

        if(lenA>lenB){
            while(k<lenA-lenB){
                nodeA=nodeA.next;
                k++;
            }
        }else{
            while (k<lenB-lenA){
                nodeB=nodeB.next;
                k++;
            }
        }

        while(nodeA!=null&&nodeB!=null){
            if(nodeA==nodeB) return nodeA;
            nodeA=nodeA.next;
            nodeB=nodeB.next;
        }
        return null;
    }

    public int length(ListNode root) {
        if(root==null) return 0;
        int n=0;
        while(root!=null){
            root=root.next;
            n++;
        }
        return n;
    }

    public static void main(String[] args) {
        int[] a={
                1,2
        };
        int[] b={
                3,4,5
        };
        int[] c={
                6,7,8
        };

        ListNode headA = LinkedUtils.arrayToLinkedList(a);
        ListNode headB = LinkedUtils.arrayToLinkedList(b);
        ListNode headC=LinkedUtils.arrayToLinkedList(c);//公共部分

        ListNode tailA=LinkedUtils.moveToTail(headA);
        ListNode tailB=LinkedUtils.moveToTail(headB);
        tailA.next=headC;
        tailB.next=headC;

        ListNode r = new Solution160().getIntersectionNode(headA, headB);
        LinkedUtils.print(r);//6->7->8
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/shu-ju-jie-gou-lei/34-xiang-jiao-lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.