跟左神学算法5 基础数据结构(链表相关)

内容：

1、链表基本结构

2、反转链表

3、打印两个有序链表的公共部分

4、判断一个链表是否为回文结构

5、单向链表划分区域

6、复制含有随机指针节点的链表

7、两个链表相交相关问题

1、链表基本结构

 1 // 单向链表:
 2     public static class Node {
 3         public int value;
 4         public Node next;
 5         public Node(int data) {
 6             this.value = data;
 7         }
 8     }
 9         
10 // 双向链表:
11     public static class DoubleNode {
12         // 双向链表的节点
13         public int value;
14         public DoubleNode last;        // 前一个节点
15         public DoubleNode next;        // 后一个节点
16         
17         public DoubleNode(int data) {
18             this.value = data;
19         }
20     }
21     
22 // 输出链表:
23     public static void printLinkedList(Node node) {
24         // 打印单向链表
25         System.out.print("Linked List: ");
26         while (node != null) {
27             System.out.print(node.value + " ");
28             node = node.next;
29         }
30         System.out.println();
31     }    
32         
33     public static void printDoubleLinkedList(DoubleNode head) {
34         // 输出双向链表
35         System.out.print("Double Linked List: ");
36         DoubleNode end = null;
37         while (head != null) {
38             System.out.print(head.value + " ");
39             end = head;
40             head = head.next;
41         }
42         System.out.print("| ");
43         while (end != null) {
44             System.out.print(end.value + " ");
45             end = end.last;
46         }
47         System.out.println();
48     }
49         
50 // 求链表长度:
51     public static int getLinkListLength(Node head) {
52         int length = 0;
53         while (head != null) {
54             length++;
55             head = head.next;
56         }
57         return length;
58     }
59         
60 // 数组和链表之间的转换:            
61     // convert the linklist to array
62     public static int[] LinkListToArray(Node head) {
63         if (head == null) {
64             return null;
65         }
66         int length = getLinkListLength(head);
67         int[] arr = new int[length];
68         int cur = 0;
69         while (head != null) {
70             arr[cur++] = head.value;
71             head = head.next;
72         }
73         
74         return arr;
75     }
76                 
77     // convert the array to linklist
78     public static Node ArrayToLinkList(int[] arr) {
79         if (arr == null || arr.length == 0) {
80             return null;
81         }
82         Node head = new Node(arr[0]);
83         Node n = head;
84         for (int i = 1; i < arr.length; i++) {
85             n.next = new Node(arr[i]);
86             n = n.next;
87         }
88                         
89         return head;
90     }

2、反转链表

问题描述：

反转单向链表和双向链表
要求时间复杂度: O(N) 额外空间复杂度: O(1)

代码：

 1 public class ReverseList {
 2     public static class Node {
 3         // 单向链表的节点
 4         public int value;
 5         public Node next;
 6 
 7         public Node(int data) {
 8             this.value = data;
 9         }
10     }
11 
12     public static class DoubleNode {
13         // 双向链表的节点
14         public int value;
15         public DoubleNode last;
16         public DoubleNode next;
17 
18         public DoubleNode(int data) {
19             this.value = data;
20         }
21     }
22     
23     public static Node reverseList(Node head) {
24         // 反转单向链表
25         Node pre = null;
26         Node next = null;
27         while (head != null) {
28             next = head.next;
29             head.next = pre;
30             pre = head;
31             head = next;
32         }
33         return pre;
34     }
35 
36     public static DoubleNode reverseList(DoubleNode head) {
37         // 反转双向链表
38         DoubleNode pre = null;
39         DoubleNode next = null;
40         while (head != null) {
41             next = head.next;
42             head.next = pre;
43             head.last = next;
44             pre = head;
45             head = next;
46         }
47         return pre;
48     }
49 
50     public static void printLinkedList(Node head) {
51         // 输出单向链表
52         System.out.print("Linked List: ");
53         while (head != null) {
54             System.out.print(head.value + " ");
55             head = head.next;
56         }
57         System.out.println();
58     }
59 
60     public static void printDoubleLinkedList(DoubleNode head) {
61         // 输出双向链表
62         System.out.print("Double Linked List: ");
63         DoubleNode end = null;
64         while (head != null) {
65             System.out.print(head.value + " ");
66             end = head;
67             head = head.next;
68         }
69         System.out.print("| ");
70         while (end != null) {
71             System.out.print(end.value + " ");
72             end = end.last;
73         }
74         System.out.println();
75     }
76 
77     public static void main(String[] args) {
78         // 1 -> 2 -> 3
79         Node head1 = new Node(1);
80         head1.next = new Node(2);
81         head1.next.next = new Node(3);
82         printLinkedList(head1);
83         printLinkedList(reverseList(head1));
84         
85         // 1 -> 2 -> 3 -> 4   |   1 <- 2 <- 3 <- 4
86         DoubleNode head2 = new DoubleNode(1);
87         head2.next = new DoubleNode(2);
88         head2.next.last = head2;
89         head2.next.next = new DoubleNode(3);
90         head2.next.next.last = head2.next;
91         head2.next.next.next = new DoubleNode(4);
92         head2.next.next.next.last = head2.next.next;
93         printDoubleLinkedList(head2);
94         printDoubleLinkedList(reverseList(head2));
95 
96     }
97 }

3、打印两个有序链表的公共部分

问题描述：

给定两个有序链表的头指针head1和head2 打印两个链表的公共部分

代码：

 1 public class PrintCommonPart {    
 2     public static class Node {
 3         public int value;
 4         public Node next;
 5         public Node(int data) {
 6             this.value = data;
 7         }
 8     }
 9 
10     public static void printCommonPart(Node head1, Node head2) {
11         // 打印两个有序链表的公共部分
12         System.out.print("Common Part: ");
13         while (head1 != null && head2 != null) {
14             if (head1.value < head2.value) {
15                 head1 = head1.next;
16             } else if (head1.value > head2.value) {
17                 head2 = head2.next;
18             } else {
19                 System.out.print(head1.value + " ");
20                 head1 = head1.next;
21                 head2 = head2.next;
22             }
23         }
24         System.out.println();
25     }
26 
27     public static void printLinkedList(Node node) {
28         // 打印链表
29         System.out.print("Linked List: ");
30         while (node != null) {
31             System.out.print(node.value + " ");
32             node = node.next;
33         }
34         System.out.println();
35     }
36 
37     public static void main(String[] args) {
38         Node node1 = new Node(2);
39         node1.next = new Node(3);
40         node1.next.next = new Node(5);
41         node1.next.next.next = new Node(6);
42 
43         Node node2 = new Node(1);
44         node2.next = new Node(2);
45         node2.next.next = new Node(5);
46         node2.next.next.next = new Node(7);
47         node2.next.next.next.next = new Node(8);
48 
49         printLinkedList(node1);
50         printLinkedList(node2);
51         printCommonPart(node1, node2);
52     }
53 }

4、判断一个链表是否为回文结构

问题描述：

给定一个链表的头节点head，请判断该链表是否为回文结构。例如： 1->2->1，返回true
1->2->2->1，返回true 15->6->15，返回true 1->2->3，返回false
进阶：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)

思路：

不限制额外空间时：

使用栈第一次遍历链表依次将节点值存入栈中然后第二次遍历链表时出栈将出栈的值和遍历到的节点值进行比较

相等就继续遍历不等就说明不是回文结构遍历到最后都没有不等的那么说明是回文结构

限制额外空间时：

一个快指针一个慢指针快指针一次走2步慢指针一次走1步当快指针走完时慢指针刚好到中点

然后从慢指针的位置开始将后面的链表逆序最后将逆序后的后半部分链表和前半部分链表对比

若两者相等就说明是回文结构否则不是另外注意: 不管最后返回什么这个链表的结构要还原然后返回!

代码：

  1 import java.util.*;
  2 
  3 public class IsPalindromeList {
  4     public static class Node {
  5         public int value;
  6         public Node next;
  7 
  8         public Node(int data) {
  9             this.value = data;
 10         }
 11     }
 12 
 13     // need n extra space
 14     public static boolean isPalindrome1(Node head) {
 15         if (head == null || head.next == null) {
 16             return true;
 17         }
 18         Stack<Node> stack = new Stack<Node>();
 19         Node cur = head;
 20         while (cur != null) {
 21             stack.push(cur);
 22             cur = cur.next;
 23         }
 24         while (head != null) {
 25             if (head.value != stack.pop().value) {
 26                 return false;
 27             }
 28             head = head.next;
 29         }
 30         return true;
 31     }
 32 
 33     // need n/2 extra space
 34     public static boolean isPalindrome2(Node head) {
 35         if (head == null || head.next == null) {
 36             return true;
 37         }
 38         Stack<Node> stack = new Stack<Node>();
 39         Node right = head.next;                        // 把慢指针往后移一位 方便后面直接从慢指针停的位置开始对比
 40         Node cur = head;
 41         while (cur.next != null && cur.next.next != null) {
 42             right = right.next;
 43             cur = cur.next.next;
 44         }    // 此时right指向右部分第一个(eg: 5个中的第四个 4个中的第三个)
 45         while (right != null) {
 46             stack.push(right);
 47             right = right.next;
 48         }
 49         while (!stack.isEmpty()) {
 50             if (head.value != stack.pop().value) {
 51                 return false;
 52             }
 53             head = head.next;
 54         }
 55         return true;
 56     }
 57 
 58     // need O(1) extra space
 59     public static boolean isPalindrome3(Node head) {
 60         if (head == null || head.next == null) {
 61             return true;
 62         }
 63         // n1是慢指针 n2是快指针
 64         Node n1 = head;
 65         Node n2 = head;
 66         while (n2.next != null && n2.next.next != null) { // find mid node
 67             n1 = n1.next;             // n1 -> mid
 68             n2 = n2.next.next;         // n2 -> end
 69         }
 70         n2 = n1.next;                 // n2 -> right part first node
 71         n1.next = null;             // mid.next -> null
 72         Node n3 = null;
 73         while (n2 != null) {         // right part convert
 74             n3 = n2.next;             // n3 -> save next node
 75             n2.next = n1;             // next of right node convert
 76             n1 = n2;                 // n1 move
 77             n2 = n3;                 // n2 move
 78         }
 79         n2 = head;                    // n2 -> save first node
 80         n3 = n1;                     // n3 -> save last node
 81         boolean res = true;
 82         while (n1 != null && n2 != null) { // check palindrome
 83             if (n1.value != n2.value) {
 84                 res = false;
 85                 break;
 86             }
 87             n1 = n1.next; // left to mid
 88             n2 = n2.next; // right to mid
 89         }
 90         
 91         // recover list
 92         n1 = n3.next;
 93         n3.next = null;
 94         while (n1 != null) { 
 95             n2 = n1.next;
 96             n1.next = n3;
 97             n3 = n1;
 98             n1 = n2;
 99         }
100         return res;
101     }
102 
103     public static void printLinkedList(Node node) {
104         System.out.print("Linked List: ");
105         while (node != null) {
106             System.out.print(node.value + " ");
107             node = node.next;
108         }
109         System.out.println();
110     }
111 
112     public static void main(String[] args) {
113 
114         Node head = null;
115         printLinkedList(head);
116         System.out.print(isPalindrome1(head) + " | ");
117         System.out.print(isPalindrome2(head) + " | ");
118         System.out.println(isPalindrome3(head) + " | ");
119         printLinkedList(head);
120         System.out.println("=========================");
121 
122         head = new Node(1);
123         printLinkedList(head);
124         System.out.print(isPalindrome1(head) + " | ");
125         System.out.print(isPalindrome2(head) + " | ");
126         System.out.println(isPalindrome3(head) + " | ");
127         printLinkedList(head);
128         System.out.println("=========================");
129 
130         head = new Node(1);
131         head.next = new Node(2);
132         printLinkedList(head);
133         System.out.print(isPalindrome1(head) + " | ");
134         System.out.print(isPalindrome2(head) + " | ");
135         System.out.println(isPalindrome3(head) + " | ");
136         printLinkedList(head);
137         System.out.println("=========================");
138 
139         head = new Node(1);
140         head.next = new Node(1);
141         printLinkedList(head);
142         System.out.print(isPalindrome1(head) + " | ");
143         System.out.print(isPalindrome2(head) + " | ");
144         System.out.println(isPalindrome3(head) + " | ");
145         printLinkedList(head);
146         System.out.println("=========================");
147 
148         head = new Node(1);
149         head.next = new Node(2);
150         head.next.next = new Node(3);
151         printLinkedList(head);
152         System.out.print(isPalindrome1(head) + " | ");
153         System.out.print(isPalindrome2(head) + " | ");
154         System.out.println(isPalindrome3(head) + " | ");
155         printLinkedList(head);
156         System.out.println("=========================");
157 
158         head = new Node(1);
159         head.next = new Node(2);
160         head.next.next = new Node(1);
161         printLinkedList(head);
162         System.out.print(isPalindrome1(head) + " | ");
163         System.out.print(isPalindrome2(head) + " | ");
164         System.out.println(isPalindrome3(head) + " | ");
165         printLinkedList(head);
166         System.out.println("=========================");
167 
168         head = new Node(1);
169         head.next = new Node(2);
170         head.next.next = new Node(3);
171         head.next.next.next = new Node(1);
172         printLinkedList(head);
173         System.out.print(isPalindrome1(head) + " | ");
174         System.out.print(isPalindrome2(head) + " | ");
175         System.out.println(isPalindrome3(head) + " | ");
176         printLinkedList(head);
177         System.out.println("=========================");
178 
179         head = new Node(1);
180         head.next = new Node(2);
181         head.next.next = new Node(2);
182         head.next.next.next = new Node(1);
183         printLinkedList(head);
184         System.out.print(isPalindrome1(head) + " | ");
185         System.out.print(isPalindrome2(head) + " | ");
186         System.out.println(isPalindrome3(head) + " | ");
187         printLinkedList(head);
188         System.out.println("=========================");
189 
190         head = new Node(1);
191         head.next = new Node(2);
192         head.next.next = new Node(3);
193         head.next.next.next = new Node(2);
194         head.next.next.next.next = new Node(1);
195         printLinkedList(head);
196         System.out.print(isPalindrome1(head) + " | ");
197         System.out.print(isPalindrome2(head) + " | ");
198         System.out.println(isPalindrome3(head) + " | ");
199         printLinkedList(head);
200         System.out.println("=========================");
201 
202     }
203 }

5、单向链表划分区域

题目描述：

将单向链表按某值划分成左边小、中间相等、右边大的形式

思路：

普通方法：

将链表节点放到数组然后partition 这个方法比较简单，直接将链表中的值保存到一个数组中，然后按照荷兰国旗的划分方式，将数组划分成左边小于那个数，中间等于那个数，右边大于那个数的形式，

(荷兰国旗问题用于快速排序中的partition过程)，划分完之后，再把数组中的值用链表的形式连接起来。但是这个方法需要　额外的O(n)的空间复杂度，且partition不能达到稳定性

进阶方法：

将链表划分成三个子链表，然后合并将原来的链表依次划分成三个链表，三个链表分别为small代表的是左边小于的部分，equal代表的是中间相等的部分，big代表的是右边的大于部分，

这三个链表都有自己的两个指针Head和Tail分别代表各自的头部和尾部，分成三个子链表之后，我们只需要遍历链表，然后和给定的值比较，按照条件，向三个链表中添加值就可以了，

最后把三个链表连接起来就可以了，但是要注意边界条件

代码：

  1 public class PartitionLinkList {
  2     public static class Node {
  3         public int value;
  4         public Node next;
  5 
  6         public Node(int data) {
  7             this.value = data;
  8         }
  9     }
 10 
 11     // get the length of linklist
 12     public static int getLinkListLength(Node head) {
 13         int length = 0;
 14         while (head != null) {
 15             length++;
 16             head = head.next;
 17         }
 18 
 19         return length;
 20     }
 21 
 22     // convert the linklist to array
 23     public static int[] LinkListToArray(Node head) {
 24         if (head == null) {
 25             return null;
 26         }
 27         int length = getLinkListLength(head);
 28         int[] arr = new int[length];
 29         int cur = 0;
 30         while (head != null) {
 31             arr[cur++] = head.value;
 32             head = head.next;
 33         }
 34 
 35         return arr;
 36     }
 37 
 38     // convert the array to linklist
 39     public static Node ArrayToLinkList(int[] arr) {
 40         if (arr == null) {
 41             return null;
 42         }
 43         Node head = new Node(arr[0]);
 44         Node n = head;
 45         for (int i = 1; i < arr.length; i++) {
 46             n.next = new Node(arr[i]);
 47             n = n.next;
 48         }
 49 
 50         return head;
 51     }
 52 
 53     // 按顺序合并两个链表(每个都可能为null)
 54     public static Node mergeLinkList(Node head1, Node head2) {
 55         if (head1 == null && head2 == null) {
 56             return null;
 57         } else if (head1 == null) {
 58             return head2;
 59         } else if (head2 == null) {
 60             return head1;
 61         } else {
 62             Node head = head1;
 63             Node tail = head;
 64             Node tail_a = head1.next;
 65             while(tail_a != null){
 66                 tail.next = tail_a;
 67                 tail = tail_a;
 68                 tail_a = tail_a.next;
 69             }
 70             Node tail_b = head2;
 71             while(tail_b != null){
 72                 tail.next = tail_b;
 73                 tail = tail_b;
 74                 tail_b = tail_b.next;
 75             }
 76             
 77             return head;
 78         }
 79     }
 80 
 81     // for test
 82     public static void printLinkedList(Node head) {
 83         while (head != null) {
 84             System.out.print(head.value + " ");
 85             head = head.next;
 86         }
 87         System.out.println();
 88     }
 89 
 90     // for test
 91     public static void printArray(int[] arr) {
 92         if (arr == null) {
 93             return;
 94         }
 95         for (int i = 0; i < arr.length; i++) {
 96             System.out.print(arr[i] + " ");
 97         }
 98         System.out.println();
 99     }
100 
101     // for test
102     public static void swap(int[] arr, int i, int j) {
103         int temp = arr[i];
104         arr[i] = arr[j];
105         arr[j] = temp;
106     }
107 
108     // partition a array
109     public static void partition(int[] arr, int num) {
110         int less = -1;
111         int more = arr.length;
112         for (int i = 0; i < more; i++) {
113             if (arr[i] < num) {
114                 swap(arr, i, ++less);
115             } else if (arr[i] > num) {
116                 swap(arr, i, --more);
117             }
118         }
119     }
120 
121     // 普通方法
122     public static Node partitionLinkList1(Node head, int num) {
123         // 将链表转换成数组 然后把数组partition一下 然后将partition后的数组再依次搞到链表中
124         int[] arr = LinkListToArray(head);
125         partition(arr, num);
126         head = ArrayToLinkList(arr);
127 
128         return head;
129     }
130 
131     // 进阶方法
132     public static Node partitionLinkList2(Node head, int num) {
133         Node sH = null; // small head
134         Node sT = null; // small tail
135         Node eH = null; // equal head
136         Node eT = null; // equal tail
137         Node bH = null; // big head
138         Node bT = null; // big tail
139         Node next = null; // save next node
140         while (head != null) {
141             // 拿出头节点head
142             next = head.next;
143             head.next = null;
144             // 根据head的值将head放入对应的链表中
145             if (head.value < num) {
146                 if (sH == null) {
147                     sH = head;
148                     sT = head;
149                 } else {
150                     sT.next = head;
151                     sT = head;
152                 }
153             } else if (head.value > num) {
154                 if (bH == null) {
155                     bH = head;
156                     bT = head;
157                 } else {
158                     bT.next = head;
159                     bT = head;
160                 }
161             } else {
162                 if (eH == null) {
163                     eH = head;
164                     eT = head;
165                 } else {
166                     eT.next = head;
167                     eT = head;
168                 }
169             }
170 
171             // 拿到原head之后的链表
172             head = next;
173         }
174 
175         // printLinkedList(sH);
176         // printLinkedList(eH);
177         // printLinkedList(bH);
178 
179         // 将三个链表合并在一起
180         return mergeLinkList(mergeLinkList(sH, eH), bH);
181     }
182 
183     // test
184     public static void main(String[] args) {
185         // test partitionLinkList1
186         Node head = new Node(1);
187         head.next = new Node(3);
188         head.next.next = new Node(6);
189         head.next.next.next = new Node(5);
190         head.next.next.next.next = new Node(8);
191         head.next.next.next.next.next = new Node(1);
192         printLinkedList(head);
193         head = partitionLinkList1(head, 5); // partition linklist
194         printLinkedList(head);
195         System.out.println("============================");
196 
197         // test partitionLinkList2
198         Node head2 = new Node(1);
199         head2.next = new Node(3);
200         head2.next.next = new Node(6);
201         head2.next.next.next = new Node(5);
202         head2.next.next.next.next = new Node(8);
203         head2.next.next.next.next.next = new Node(1);
204         printLinkedList(head2);
205         head2 = partitionLinkList2(head2, 5);
206         printLinkedList(head2);
207     }
208 
209 }

6、复制含有随机指针节点的链表

题目描述：

一种特殊的链表节点类描述如下：
public class Node{
　　public int value; // 节点值
　　public Node next; // 下一个节点
　　public Node rand;

　　public Node(int data){
　　　　this.value = data
　　}
}
rand指针是Node类中的新增的指针，这个指针可能指向链表中任意的一个节点，也可能指向null
给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中
所有结构的复制，并返回复制的新链表的头节点
进阶：不使用额外数据结构，只用有限几个变量，时间复杂度为 O(N)

思路：

 1 最快的思路:
 2     借助hash表实现 将节点拷贝(只拷贝节点的value) 然后把原节点作为key 拷贝之后的节点
 3     作为value 放入hash表中 然后依次读取原节点的next和rand 将拷贝后的节点连起来
 4 
 5 另外的思路:
 6     不用哈希表来保存对应关系，只用有限的几个变量完成所有的功能。
 7     首先从左到右遍历链表，对每个节点cur都复制生成相应的副本节点copy，然后把copy放在cur和
 8     下一个要遍历节点的中间 再从左到右遍历链表，在遍历时设置每一个副本节点的rand指针
 9     每个节点的副本节点都在自己的后一个，所以此时通过next就可以找到 以这种方式可以设置
10     每一个副本节点的rand指针 最后将原节点和副本节点分离

代码：

 1 public class CopyLinkListRand {
 2     public static class Node{
 3          public int value;        // 节点值
 4         public Node next;        // 下一个节点
 5         public Node rand;        
 6         
 7         public Node(int data){
 8             this.value = data;
 9         }
10     }
11     
12     public static void printRandLinkedList(Node head) {
13         Node cur = head;
14         System.out.print("order: ");
15         while (cur != null) {
16             System.out.print(cur.value + " ");
17             cur = cur.next;
18         }
19         System.out.println();
20         cur = head;
21         System.out.print("rand:  ");
22         while (cur != null) {
23             System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
24             cur = cur.next;
25         }
26         System.out.println();
27     }
28     
29     public static Node copyLinkListRand1(Node head){
30         if (head == null) {
31             return null;
32         }
33         HashMap<Node, Node> map = new HashMap<Node, Node>();
34         Node cur = head;
35         while(cur!=null){
36             map.put(cur, new Node(cur.value));
37             cur = cur.next;
38         }
39         cur = head;
40         while(cur!=null){
41             map.get(cur).next = map.get(cur.next);
42             map.get(cur).rand = map.get(cur.rand);
43             cur = cur.next;
44         }
45         return map.get(head);
46     }
47     
48     public static Node copyLinkListRand2(Node head){
49         if (head == null) {
50             return null;
51         }
52         Node cur = head;
53         Node next = null;
54         // copy node and link to every node
55         while (cur != null) {
56             next = cur.next;
57             cur.next = new Node(cur.value);
58             cur.next.next = next;
59             cur = next;
60         }
61         cur = head;
62         Node curCopy = null;
63         // set copy node rand
64         while (cur != null) {
65             next = cur.next.next;
66             curCopy = cur.next;
67             curCopy.rand = cur.rand != null ? cur.rand.next : null;
68             cur = next;
69         }
70         Node res = head.next;
71         cur = head;
72         // split
73         while (cur != null) {
74             next = cur.next.next;
75             curCopy = cur.next;
76             cur.next = next;
77             curCopy.next = next != null ? next.next : null;
78             cur = next;
79         }
80         return res;
81     }
82         
83     public static void main(String[] args) {    
84     }
85 }

7、两个链表相交相关问题

题目描述：

在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交

的第一个节点；如果不相交，返回null 即可。要求：如果链表1长度为N，链表2长度为M 时间复杂度O(N+M)，额外空间复杂度O(1)

思路：

分成三个问题来看：

链表是否有环
链表是否相交
如果相交返回第一个节点

代码：

  1 public class FindFirstIntersectNode {
  2     
  3     public static class Node {
  4         public int value;
  5         public Node next;
  6 
  7         public Node(int data) {
  8             this.value = data;
  9         }
 10     }
 11     
 12     public static Node getLoopNode(Node head){
 13         // 判断单链表是否成环 成环返回环的第一个节点 否则返回null
 14         if (head == null || head.next == null || head.next.next == null) {
 15             return null;
 16         }
 17         Node n1 = head.next;         // n1 -> slow
 18         Node n2 = head.next.next;     // n2 -> fast
 19         while (n1 != n2) {
 20             if (n2.next == null || n2.next.next == null) {
 21                 return null;
 22             }
 23             n2 = n2.next.next;
 24             n1 = n1.next;
 25         }
 26         n2 = head; // n2 -> walk again from head
 27         while (n1 != n2) {
 28             n1 = n1.next;
 29             n2 = n2.next;
 30         }
 31         return n1;
 32     }
 33     
 34     public static Node getIntersectNode(Node head1, Node head2){
 35         if(head1 == null && head2 == null){
 36             return null;
 37         }
 38         Node loop1 = getLoopNode(head1);
 39         Node loop2 = getLoopNode(head2);
 40         if(loop1 == null && loop2 == null){
 41             // 两个无环链表的相交问题
 42             return noloop(head1, head2);
 43         }
 44         if(loop1 != null && loop2 != null){
 45             // 两个有环链表的相交问题
 46             return bothLoop(head1, loop1, head2, loop2);
 47         }
 48         // 两个链表中一个有环 一个无环 不可能相交
 49         return null;
 50     }
 51     
 52     public static Node noloop(Node head1, Node head2){
 53         // 两个无环链表的相交问题
 54         // 1 不可能相交
 55         if(head1 == null || head2 == null){
 56             return null;
 57         }
 58         
 59         // 2 可能相交
 60         Node cur1 = head1;
 61         Node cur2 = head2;
 62         
 63         // n代表两个链表长度的差值关系
 64         int n = 0;
 65         while (cur1.next != null) {
 66             n++;
 67             cur1 = cur1.next;
 68         }
 69         while (cur2.next != null) {
 70             n--;
 71             cur2 = cur2.next;
 72         }
 73         // 两个无环链表最后一个节点不相等 一定不相交
 74         if (cur1 != cur2) {
 75             return null;
 76         }
 77         // 两个无环链表最后一个节点相等 一定相交
 78         // 定位谁是长链表 谁是短链表
 79         cur1 = n > 0 ? head1 : head2;
 80         cur2 = cur1 == head1 ? head2 : head1;
 81         // 移动长链表的cur
 82         n = Math.abs(n);
 83         while (n != 0) {
 84             n--;
 85             cur1 = cur1.next;
 86         }
 87         // cur1和cur2相等的位置就是第一次相交的位置
 88         while (cur1 != cur2) {
 89             cur1 = cur1.next;
 90             cur2 = cur2.next;
 91         }
 92         return cur1;
 93     }
 94     
 95     public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
 96         Node cur1 = null;
 97         Node cur2 = null;
 98         if (loop1 == loop2) {
 99             // 类似上述无环链表相交的情况
100             cur1 = head1;
101             cur2 = head2;
102             int n = 0;
103             while (cur1 != loop1) {
104                 n++;
105                 cur1 = cur1.next;
106             }
107             while (cur2 != loop2) {
108                 n--;
109                 cur2 = cur2.next;
110             }
111             // 定位谁是长链表 谁是短链表
112             cur1 = n > 0 ? head1 : head2;
113             cur2 = cur1 == head1 ? head2 : head1;
114             // 移动长链表的cur
115             n = Math.abs(n);
116             while (n != 0) {
117                 n--;
118                 cur1 = cur1.next;
119             }
120             // cur1和cur2相等的位置就是第一次相交的位置
121             while (cur1 != cur2) {
122                 cur1 = cur1.next;
123                 cur2 = cur2.next;
124             }
125             return cur1;
126         } else {
127             cur1 = loop1.next;
128             while (cur1 != loop1) {
129                 if (cur1 == loop2) {
130                     // 相交
131                     return loop1;
132                 }
133                 cur1 = cur1.next;
134             }
135             // 根本不相交
136             return null;
137         }
138     }
139     
140     public static void main(String[] args) {
141         
142     }
143 }