算法初级——两个单链表相交的有关问题

两个单链表相交的一系列问题
【题目】 在本题中,单链表可能有环,也可能无环。给定两个单链表的头节点 head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数, 如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null 即可。
要求:如果链表1的长度为N,链表2的长度为M,时间复杂度请达到 O(N+M),额外空间复杂度请达到O(1)。
/*
* 1.如何判断单链表有环无环
* 如果单链表有环,返回第一个入环节点,如果无环,返回空,可用哈希表实现(hashset);
* 不用哈希表实现单链表有环判断,准备两个指针,快指针每次走两步,慢指针每次走一步,如果快指针在走的过程中返回null,则无环
* 如果有环,慢指针会和快指针在环上相遇,相遇后,快指针回到链表开头,每次走一步,快指针和慢指针会在入环节点处相遇。
* 2.两个无环单链表第一个相交的节点
* 哈希表实现,链表1所有节点放入map,链表2每遍历一个节点就去哈希表查一遍,第一个在的就是第一个相交节点。
* 不用hashmap:先遍历链表1,统计链表1 的长度,拿到链表1 的最后一个节点,然后遍历链表2,统计链表2 的长度,
* 拿到链表2 的最后一个节点,先判断end1是否等于end2(内存地址);如果不相等,则不可能相交,如果end1等于end2,长度较长的先走差值部分,
* 然后开始同时走,最后一起到达节点处。
* 3.两个有环单链表第一个相交的节点
* 两个有环分为三种情况,
* a.各自为环
* 如果loop1.next永远不等于loop2,则不相交
* b.先相交,然后共用一个环
* 从入环节点切分,只考虑入环前的链表,转换为两个无环单链表相交问题
* c.在一个环的不同节点入环
* loop1.next=loop2,返回loop1和loop2都可以。
*/

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
public class 单链表相交 {
    public static class Node{
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }
    }
    public static Node getIntersectNode(Node head1,Node head2) {
        if(head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if(loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        if(loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }
    //判断是否有环,如果有环返回入环节点,否则返回空
    public static Node getLoopNode(Node head) {
        if(head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node n1 = head.next; //慢节点
        Node n2 = head.next.next; //快节点
        while(n1 != n2) {
            if(n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        n2 = head; //快节点返回头部
        while(n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
    //两个无环单链表判断交点
    public static Node noLoop(Node head1, Node head2) {
        if(head1 == null || head2 == null) {
            return null;
        }
        Node c1 = head1;
        Node c2 = head2;
        int n = 0;
        while(c1.next != null) {
            n++;
            c1 = c1.next;
        }
        while(c2.next != null) {
            n--;
            c2 = c2.next;
        }
        if(c1 != c2) {
            return null;
        }
        c1 = n > 0 ? head1 : head2;
        c2 = c1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while(n != 0) {
            n--;
            c1 = c1.next;
        }
        while(c1 != c2) {
            c1 = c1.next;
            c2 = c2.next;
        }
        return c1; 
    }
    //两个有环单链表的相交节点
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node c1 = null;
        Node c2 = null;
        if(loop1 == loop2) {
            c1 = head1;
            c2 = head2;
            int n = 0;
            while(c1.next != loop1) {
                n++;
                c1 = c1.next;
            }
            while(c2.next != loop2) {
                n--;
                c2 = c2.next;
            }
            c1 = n > 0 ? head1 : head2;
            c2 = c1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while(n != 0) {
                n--;
                c1 = c1.next;
            }
            while(c1 != c2) {
                c1 = c1.next;
                c2 = c2.next;
            }
            return c1;
        }else {
            c1 = loop1.next;
            while(c1 != loop1) {
                if(c1 == loop2) {
                    return loop1;
                }
                c1 = c1.next;
            }
        }
        return null;   
    }
   
    public static void main(String[] args) {
       
    }

}
0 条评论
发表一条评论