-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
101 lines (96 loc) · 2.72 KB
/
Program.cs
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
using System;
namespace IntersectionOfTwoLinkedLists
{
class ListNode
{
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
class Program
{
static void Main(string[] args)
{
ListNode a1 = new ListNode(4);
ListNode a2 = new ListNode(1);
ListNode a3 = new ListNode(8);
ListNode a4 = new ListNode(4);
ListNode a5 = new ListNode(5);
a1.next = a2;
a2.next = a3;
a3.next = a4;
a4.next = a5;
ListNode b1 = new ListNode(5);
ListNode b2 = new ListNode(0);
ListNode b3 = new ListNode(1);
ListNode b4 = new ListNode(8);
ListNode b5 = new ListNode(4);
ListNode b6 = new ListNode(5);
b1.next = b2;
b2.next = b3;
b3.next = b4;
b4.next = b5;
b5.next = b6;
ListNode res = GetIntersectionNode(a1, b2);
PrintList(res);
}
static void PrintList(ListNode list)
{
while (list != null)
{
Console.Write(list.val + "->");
list = list.next;
}
Console.Write("null");
}
static int GetLen(ListNode head)
{
int len = 0;
while (head != null)
{
len++;
head = head.next;
}
return len;
}
static ListNode CutList(ListNode head, int lenLong, int lenShort)
{
for (int i = 0; i < lenLong - lenShort; i++)
{
head = head.next;
}
return head;
}
static public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
int LenA = GetLen(headA);
int LenB = GetLen(headB);
if (LenA >= LenB)
headA = CutList(headA, LenA, LenB);
else
headB = CutList(headB, LenB, LenA);
while (headA != null && headB != null && headA != headB)
{
headA = headA.next;
headB = headB.next;
}
return headA;
}
public ListNode GetIntersectionNode_HashSet(ListNode headA, ListNode headB)
{
var set = new HashSet<ListNode>();
while (headA != null)
{
set.Add(headA);
headA = headA.next;
}
while (headB != null)
{
if (set.Contains(headB))
return headB;
headB = headB.next;
}
return null;
}
}
}