链表专题 2. 求链表交点

57 阅读 0 评论 38 点赞

我是靠谱客的博主英勇羽毛，最近开发中收集的这篇文章主要介绍链表专题 2. 求链表交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

leecode

题目描述：
给出两个单链表，求他们的公共交点

思路：
如果两条链表有交点x，那么他们在x后面的节点都是相同的。
先求出链表长度差 dif，遍历其中一条链表使他们的长度相同，然后一顿乱搞。

/**
 * 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) {
        int lena = 0, lenb = 0;
        ListNode a = headA, b = headB;
        while(headA != null){
            headA = headA.next;
            lena++;
        }
        while(headB != null){
            headB = headB.next;
            lenb++;
        }

        if(lena > lenb){
            int dif = lena-lenb;
            while(a!=null && dif>0){
                a = a.next;
                dif--;
            }
            while(a != b){
                a = a.next;
                b = b.next;
            }
            return a;
        }
        else{
            int dif = lenb-lena;
            while(b!=null && dif>0){
                b = b.next;
                dif--;
            }
            while(a != b){
                a = a.next;
                b = b.next;
            }
            return b;
        }

    }
}