forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathIntersectionOfTwoLinkedLists.java
More file actions
72 lines (69 loc) · 1.99 KB
/
IntersectionOfTwoLinkedLists.java
File metadata and controls
72 lines (69 loc) · 1.99 KB
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
/*
Author: King, wangjingui@outlook.com
Date: Nov 28, 2014
Problem: Intersection of Two Linked Lists
Difficulty: Easy
Source: https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
Notes:
Write a program to find the node at which the intersection of two singly linked lists begins.
Hints:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
Solution: Two iteration.
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur = headA;
int lenA = 0, lenB = 0;
while (cur != null) {
++lenA;
cur = cur.next;
}
cur = headB;
while (cur != null) {
++lenB;
cur = cur.next;
}
if (lenA >= lenB) {
int diff = lenA - lenB;
while (diff > 0) {
headA = headA.next;
--diff;
}
while (headA != null && headB != null) {
if(headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
} else {
int diff = lenB - lenA;
while (diff > 0) {
headB = headB.next;
--diff;
}
while (headA != null && headB != null) {
if(headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
}
return null;
}
}