-
Notifications
You must be signed in to change notification settings - Fork 2
/
PalindromeLinkedList.java
114 lines (93 loc) · 2.3 KB
/
PalindromeLinkedList.java
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
113
114
package LinkedList._234_Palindrome_Linked_List;
import DataStructure.ListNode;
import java.util.Stack;
/**
* Created by hengwang on 2017-05-28.
*
* Given a singly linked list, determine if it is a palindrome.
*
* Follow up:
* Could you do it in O(n) time and O(1) space?
*
*/
public class PalindromeLinkedList {
/**
* 1. Copy the original linked list
* 2. Reverse the original one
* 3. Compare the two
* @param head
* @return
*/
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// Copy the original Linked List
ListNode copyHead = new ListNode(head.data);
ListNode copyNext = copyHead;
ListNode runner = head.next;
copyHead.next = copyNext;
while (runner != null) {
ListNode n = new ListNode(runner.data);
copyNext.next = n;
copyNext = n;
runner = runner.next;
}
// Reverse the original Linked list
ListNode current = head;
ListNode reversedHead = current;
while (current != null) {
ListNode next = current.next;
current.next = reversedHead;
reversedHead = current;
current = next;
}
head.next = null;
// Compare the reversed linked list with the copy linked list
while (reversedHead != null) {
if (reversedHead.data != copyHead.data) {
return false;
}
reversedHead = reversedHead.next;
copyHead = copyHead.next;
}
return true;
}
/**
* Using runner approach and stack to store the half front nodes. And compare to the rest of the nodes.
* @param head
* @return
*/
public boolean isPalindrome_IterateApproach(ListNode head) {
if (head == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
Stack<Integer> stack = new Stack<>();
while (fast != null && fast.next != null) {
stack.push(slow.data);
slow = slow.next;
fast = fast.next.next;
}
/* Has odd number of elements, so skip the middle element*/
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.data != stack.pop()) {
return false;
}
slow = slow.next;
}
return true;
}
/**
*
* @param head
* @return
*/
public boolean isPalindrome_LinearTime(ListNode head) {
return true;
}
}