/
FirstCommonNodesInLists.java
76 lines (63 loc) · 2.12 KB
/
FirstCommonNodesInLists.java
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
/**
* Created by Yang on 2017/4/21.
* 输入两个链表,找出它们的第一个公共结点。
*/
public class FirstCommonNodesInLists {
private static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
public String toString() {
if(next == null) {
return val + "";
}
return val + ", " + this.next;
}
}
public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null) {
return null;
}
int length1 = getListLength(pHead1);
int length2 = getListLength(pHead2);
int lengthDiff = length1 - length2;
ListNode longListHead = pHead1;
ListNode shortListHead = pHead2;
if(length1 < length2) {
lengthDiff = length2 - length1;
longListHead = pHead2;
shortListHead = pHead1;
}
for (int i = 0; i < lengthDiff; i++) {
longListHead = longListHead.next;
}
while(longListHead != null && shortListHead != null && longListHead != shortListHead) {
longListHead = longListHead.next;
shortListHead = shortListHead.next;
}
ListNode firstCommonNode = longListHead;
return firstCommonNode;
}
private int getListLength(ListNode head) {
int length = 0;
while(head != null) {
length++;
head = head.next;
}
return length;
}
public static void main(String[] args) {
FirstCommonNodesInLists firstCommonNodesInLists = new FirstCommonNodesInLists();
ListNode list1 = new ListNode(1);
list1.next = new ListNode(2);
list1.next.next = new ListNode(3);
list1.next.next.next = new ListNode(6);
list1.next.next.next.next = new ListNode(7);
ListNode list2 = new ListNode(4);
list2.next = new ListNode(5);
list2.next.next = list1.next.next.next;
System.out.println(firstCommonNodesInLists.findFirstCommonNode(list1, list2));
}
}