Leetcode Answers 160

继续刷Easy难度,毕竟Easy。

题目:
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

1
2
3
4
5
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.

思路:
乍一看是要从头开始两边对比,但是又不是说sorted list,所以要换个角度。根据Example,找的是c1,而c1开始的list就是两边共有的list,于是就可以想到,先把两边的长度差出来的部分移动过去,因为intersection一定不在这里,然后当两边剩下的长度相同的时候,逐个对比。那么怎么找到长度呢?再遍历一遍呗。因为遍历是符合O(n)的,而两个variable存长度,也是符合O(1)的,那么就可以了。

Answer:

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
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA, p2 = headB;
int l1 = 0, l2 = 0;
while(p1!=null){
p1 = p1.next;
++l1;
}
while(p2!=null){
p2 = p2.next;
++l2;
}
p1 = headA;
p2 = headB;
if(l1 > l2){
for(int i=0;i<l1-l2;i++){
p1 = p1.next;
}
}else{
for(int i=0;i<l2-l1;i++){
p2 = p2.next;
}
}
while(p1!=p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}

以上。

17-04-23
@Sturbridge