Skip to content

Commit b9ac7fe

Browse files
jianminchenjianminchen
committed
check in source code
1 parent 76279a4 commit b9ac7fe

File tree

2 files changed

+292
-0
lines changed

2 files changed

+292
-0
lines changed

‎2017 July -/Leetcode 234 Palindrome Linked List.cs

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode_234_Palindrome_Linked_List
8+
{
9+
/// <summary>
10+
/// Leetcode 234 Palindrome linked list
11+
/// https://leetcode.com/problems/palindrome-linked-list/description/
12+
/// Could you do it in O(n) time and O(1) space?
13+
/// </summary>
14+
class Program
15+
{
16+
public class ListNode {
17+
public int val;
18+
public ListNode next;
19+
public ListNode(int x) { val = x; }
20+
}
21+
22+
static void Main(string[] args)
23+
{
24+
RunTestcase();
25+
}
26+
27+
public static void RunTestcase()
28+
{
29+
var head = new ListNode(1);
30+
var node2 = new ListNode(2);
31+
32+
head.next = node2;
33+
34+
var result = IsPalindrome(head);
35+
}
36+
37+
public static void RunTestcase2()
38+
{
39+
var head = new ListNode(1);
40+
var node2 = new ListNode(2);
41+
var node3 = new ListNode(2);
42+
var node4 = new ListNode(1);
43+
44+
head.next = node2;
45+
node2.next = node3;
46+
node3.next = node4;
47+
48+
var result = IsPalindrome(head);
49+
}
50+
51+
/// <summary>
52+
/// design function using three API
53+
/// 1. reverse linked list
54+
/// 2. get length of linked list
55+
/// 3. get kth linked list node
56+
/// </summary>
57+
/// <param name="head"></param>
58+
/// <returns></returns>
59+
public static bool IsPalindrome(ListNode head)
60+
{
61+
if (head == null)
62+
return true;
63+
64+
if (head.next == null)
65+
return true;
66+
67+
var length = getLinkedListLength(head);
68+
var isEven = length % 2 == 0;
69+
var back = head;
70+
var front = getNodeGivenK(head, length/ 2);
71+
if (!isEven)
72+
{
73+
front = front.next;
74+
}
75+
76+
var reversed = reverseLinkedList(front);
77+
78+
// compare two linked list one element a time
79+
var index = 0;
80+
while (index < length / 2)
81+
{
82+
if (back.val != reversed.val)
83+
return false;
84+
85+
back = back.next;
86+
reversed = reversed.next;
87+
index++;
88+
}
89+
90+
return true;
91+
}
92+
93+
/// <summary>
94+
/// reverse a linked list using O(N) time and O(1) space
95+
/// </summary>
96+
/// <param name="head"></param>
97+
private static ListNode reverseLinkedList(ListNode head)
98+
{
99+
if (head == null)
100+
return null;
101+
if (head.next == null)
102+
return head;
103+
104+
var next = head.next;
105+
var reversed = reverseLinkedList(next);
106+
107+
head.next = null;
108+
next.next = head;
109+
110+
return reversed;
111+
}
112+
113+
private static ListNode getNodeGivenK(ListNode head, int k)
114+
{
115+
if (k == 0)
116+
return head;
117+
118+
int index = 0;
119+
var iterate = head;
120+
while (index < k)
121+
{
122+
iterate = iterate.next;
123+
index++;
124+
}
125+
126+
return iterate;
127+
}
128+
129+
private static int getLinkedListLength(ListNode head)
130+
{
131+
if (head == null)
132+
return 0;
133+
134+
var index = 0;
135+
var iterate = head;
136+
while (iterate != null)
137+
{
138+
index++;
139+
140+
iterate = iterate.next;
141+
}
142+
143+
return index;
144+
}
145+
}
146+
}

‎Leetcode 234 Palindrome Linked List.cs

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode_234_Palindrome_Linked_List
8+
{
9+
/// <summary>
10+
/// Leetcode 234 Palindrome linked list
11+
/// https://leetcode.com/problems/palindrome-linked-list/description/
12+
/// Could you do it in O(n) time and O(1) space?
13+
/// </summary>
14+
class Program
15+
{
16+
public class ListNode {
17+
public int val;
18+
public ListNode next;
19+
public ListNode(int x) { val = x; }
20+
}
21+
22+
static void Main(string[] args)
23+
{
24+
RunTestcase();
25+
}
26+
27+
public static void RunTestcase()
28+
{
29+
var head = new ListNode(1);
30+
var node2 = new ListNode(2);
31+
32+
head.next = node2;
33+
34+
var result = IsPalindrome(head);
35+
}
36+
37+
public static void RunTestcase2()
38+
{
39+
var head = new ListNode(1);
40+
var node2 = new ListNode(2);
41+
var node3 = new ListNode(2);
42+
var node4 = new ListNode(1);
43+
44+
head.next = node2;
45+
node2.next = node3;
46+
node3.next = node4;
47+
48+
var result = IsPalindrome(head);
49+
}
50+
51+
/// <summary>
52+
/// design function using three API
53+
/// 1. reverse linked list
54+
/// 2. get length of linked list
55+
/// 3. get kth linked list node
56+
/// </summary>
57+
/// <param name="head"></param>
58+
/// <returns></returns>
59+
public static bool IsPalindrome(ListNode head)
60+
{
61+
if (head == null)
62+
return true;
63+
64+
if (head.next == null)
65+
return true;
66+
67+
var length = getLinkedListLength(head);
68+
var isEven = length % 2 == 0;
69+
var back = head;
70+
var front = getNodeGivenK(head, length/ 2);
71+
if (!isEven)
72+
{
73+
front = front.next;
74+
}
75+
76+
var reversed = reverseLinkedList(front);
77+
78+
// compare two linked list one element a time
79+
var index = 0;
80+
while (index < length / 2)
81+
{
82+
if (back.val != reversed.val)
83+
return false;
84+
85+
back = back.next;
86+
reversed = reversed.next;
87+
index++;
88+
}
89+
90+
return true;
91+
}
92+
93+
/// <summary>
94+
/// reverse a linked list using O(N) time and O(1) space
95+
/// </summary>
96+
/// <param name="head"></param>
97+
private static ListNode reverseLinkedList(ListNode head)
98+
{
99+
if (head == null)
100+
return null;
101+
if (head.next == null)
102+
return head;
103+
104+
var next = head.next;
105+
var reversed = reverseLinkedList(next);
106+
107+
head.next = null;
108+
next.next = head;
109+
110+
return reversed;
111+
}
112+
113+
private static ListNode getNodeGivenK(ListNode head, int k)
114+
{
115+
if (k == 0)
116+
return head;
117+
118+
int index = 0;
119+
var iterate = head;
120+
while (index < k)
121+
{
122+
iterate = iterate.next;
123+
index++;
124+
}
125+
126+
return iterate;
127+
}
128+
129+
private static int getLinkedListLength(ListNode head)
130+
{
131+
if (head == null)
132+
return 0;
133+
134+
var index = 0;
135+
var iterate = head;
136+
while (iterate != null)
137+
{
138+
index++;
139+
140+
iterate = iterate.next;
141+
}
142+
143+
return index;
144+
}
145+
}
146+
}

0 commit comments

Comments
 (0)