两个链表找首个共同节点

明确问题

两个链表，说明有两个头节点（这明显是句废话！）
共同节点，说明这两个链表相会了（就是都指向了同一个节点。）

如图：

明确思路

首先我们要判断的不是“值”，相不相等，而是“指针”（Java里应该叫做引用。）

解法1：暴力（不推荐！）

如果你用暴力的话，这道题就没有意义了！（这句话说的 的确很中肯。）

循环得出两个链表每个结点的 next（尾部：用来存放下一个节点引用的），然后再一个一个的对比

时间复杂度：n的平方

解法2：找规律（推荐！）

链表只能从前往后找，这让这道问题的难度增加了。

因为我们不知道 两个链表的 共同节点 之前是不是有 相同个数的节点，相同的话就好办了，但一般不相同。

首先这两个链表是不一样的，但如果我们只针对他们的共同部分，就变得 “一样” 了

如图：

把长链表 “多余” 的部分 咔嚓掉 就好办了 ……

	/**
     * 节点结构定义
     */
    public static class ListNode{
        public int value;
        public ListNode next;

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

    /**
     * 获得链表长度
     */
    public static int len(ListNode node){
        ListNode n = node;
        int len = 0;
        if (node == null){
            return len;
        }
        while (true){
            if (n.next == null){
                len++;
                break;
            }
            n = n.next;
            len++;
        }
        return len;
    }

    public static ListNode sameNode(ListNode node1,ListNode node2){

        ListNode n1 = node1,n2 = node2;
        int len1 = len(node1),len2 = len(node2);
        if (len1 > len2){
            for (int i = 0;i < (len1-len2);i++){
                n1 = n1.next;
            }
            while (true){
                if (n1.next == null || n2.next == null){
                    return null;
                }
                if(n1.next == n2.next){
                    return n1.next;
                }
                n1 = n1.next;
                n2 = n2.next;
            }
        }else{
            for (int i = 0;i < (len2-len1);i++){
                n2 = n2.next;
            }
            while (true){
                if (n1.next == null || n2.next == null){
                    return null;
                }
                if(n1.next == n2.next){
                    return n1.next;
                }
                n1 = n1.next;
                n2 = n2.next;
            }
        }
    }

    public static void main(String[] args) {
        //我们打算 node1 作为 第一个链表的 头节点
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        //我们打算 node3 作为 第二个链表的 头节点
        ListNode node3 = new ListNode(3);
        //我们打算 node4 作为 两个链表的 首个 共同节点
        ListNode node4 = new ListNode(4);
        //我们打算 node5 和 node6 作为 两个链表 之后的 共同节点
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);

        //建立连接 ……

        node1.next = node2;
        node2.next = node4;

        node3.next = node4;

        node4.next = node5;
        node5.next = node6;
        //开始测试
        System.out.println(sameNode(node1,node3).value);

    }


  

 

  
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
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
 

输出结果：

4

没有什么问题！！

总结
看两个链表的共同部分
先求两个链表的长度
以 短的 那个 作为基准（因为重复的部分就是 那个 短链表！！）
把长的那个 “咔嚓” 了，这样两个就一样 “短” 了

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/108890577