Leetcode Intersection of Two Linked Lists
10350 ワード
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lena = count(headA);
int lenb = count(headB);
int diff = 0;
ListNode* longer = NULL;
ListNode* shorter= NULL;
if (lena > lenb) {
diff = lena - lenb;
longer = headA;
shorter= headB;
} else {
diff = lenb - lena;
longer = headB;
shorter= headA;
}
longer = forward(longer, diff);
while (longer != shorter) {
longer = forward(longer, 1);
shorter= forward(shorter, 1);
}
return longer;
}
ListNode* forward(ListNode* head, int step) {
while(head != NULL) {
if (step-- <= 0) {
break;
}
head = head->next;
}
return head;
}
int count(ListNode* head) {
int res = 0;
while (head != NULL) {
head = head->next;
res++;
}
return res;
}
};
Leetcodeも可視化され、ますますハイエンドになりました
第2ラウンド:
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:
null
. 1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 // 20:08
10 class Solution {
11 public:
12 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
13 ListNode* cura = headA;
14 ListNode* curb = headB;
15
16 int na = 0, nb = 0;
17
18 while (cura != NULL) {
19 na++;
20 cura = cura->next;
21 }
22
23 while (curb != NULL) {
24 nb++;
25 curb = curb->next;
26 }
27 ListNode* prewalk = NULL;
28
29 int diff = 0;
30 if (na > nb) {
31 prewalk = headA;
32 diff = na - nb;
33 } else if (na < nb) {
34 prewalk = headB;
35 diff = nb - na;
36 }
37 while (diff--) {
38 prewalk = prewalk->next;
39 }
40
41 cura = headA;
42 curb = headB;
43
44 if (na > nb) {
45 cura = prewalk;
46 } else if (na < nb){
47 curb = prewalk;
48 }
49
50 while (cura != curb) {
51 cura = cura->next;
52 curb = curb->next;
53 }
54 return cura;
55 }
56 };