FilesExpand file tree

 master

/

IntersectionOfTwoLinkedList.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

112 lines (97 loc) · 2.71 KB

 master

/

IntersectionOfTwoLinkedList.java

Copy path

Top

File metadata and controls

• Code
• Blame

112 lines (97 loc) · 2.71 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2

↘

c1 → c2 → c3

↗

B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

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.*/

/**

* 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) {

int lengthA = getLength(headA);

int lengthB = getLength(headB);

if (lengthA > lengthB) {

int dif = lengthA - lengthB;

while (dif > 0) {

headA = headA.next;

dif--;

}

} else {

int dif = lengthB - lengthA;

while (dif > 0) {

headB = headB.next;

dif--;

}

}

while (headA != null && headB != null) {

if (headA == headB) {

return headA;

}

headA = headA.next;

headB = headB.next;

}

return headA;

}

public int getLength(ListNode head) {

int res = 0;

while (head != null) {

head = head.next;

res++;

}

return res;

}

}

// Concise

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

int lenA = length(headA), lenB = length(headB);

// move headA and headB to the same start point

while (lenA > lenB) {

headA = headA.next;

lenA--;

}

while (lenA < lenB) {

headB = headB.next;

lenB--;

}

// find the intersection until end

while (headA != headB) {

headA = headA.next;

headB = headB.next;

}

return headA;

}

private int length(ListNode node) {

int length = 0;

while (node != null) {

node = node.next;

length++;

}

return length;

}

// A tricky solution

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

if( null==headA || null==headB )

return null;

ListNode curA = headA, curB = headB;

while( curA!=curB){

curA = curA==null?headB:curA.next;

curB = curB==null?headA:curB.next;

}

return curA;

}