LeetCode练习题—两个链表的第一个公共结点（Java）

62 阅读 0 评论 41 点赞

我是靠谱客的博主大气小熊猫，这篇文章主要介绍LeetCode练习题—两个链表的第一个公共结点（Java），现在分享给大家，希望可以做个参考。

题目描述：

输入两个链表，找出它们的第一个公共节点。

注意：

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

示例：

在这里插入图片描述

思路：

输入两个链表，找出它们的第一个公共节点，可以分情况讨论：

1、若任意一个链表为空，那么直接返回null；
2、若为一般情况，要找公共起点，那么可以先让两个链表的长度保持一致；首先分别获取两个的长度 lenA 和 lenB，找到较长的链表longHead，让他向后走step（step= lenA - lenB）步（假设lenA > lenB)，此时两个链表长度一致，然后在两个链表不为空，且两链表结点不同的情况下，让两个链表同步向后走；若遇到相同的结点即返回；此时的结点即为两个链表的第一个公共结点

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
/**
* Definition for singly-linked list.
* public class Node {
*     int val;
*     Node next;
*     Node(int x) {
*         val = x;
*         next = null;
*     }
*     }
*/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public Node getIntersectionNode(Node headA, Node headB) {
    //任意一个链表为空直接返回null
    if(headA == null || headB == null){
            return null;
        }
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    int step = lenA - lenB;
    Node longHead = headA;
    Node shortHead = headB;
    //判断连个链表之间那个链表更长
    if(step<0){  
        longHead = headB;
        shortHead = headA;
        step = lenB - lenA;
    }
    //长链表向后走至两个链表相同
    for(int i = 0;i<step;i++){  
        longHead = longHead.next;;
    }
    //找到第一个公共结点
    while (longHead != null && shortHead != null && longHead != shortHead) {
        longHead = longHead.next;
        shortHead = shortHead.next;
    }
    return longHead;
}

//获取链表的长度
private int getLength(Node head){
    int count = 0;
    while(head != null){
        head = head.next;
        count++;
    }
    return count;
}