-
Notifications
You must be signed in to change notification settings - Fork 0
/
234. Palindrome Linked List
110 lines (101 loc) · 3.51 KB
/
234. Palindrome Linked List
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
odd
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode headCopy = new ListNode(head.val);
headCopy.next = head.next;
boolean palindromeEven = isPalindromeEven(head);
boolean palindromeOdd = isPalindromeOdd(headCopy);
return palindromeOdd || palindromeEven;
}
// чётный 1-2-2-1
private boolean isPalindromeEven(ListNode head) {
ListNode lhs = null;
ListNode current = head;
ListNode rhs = head.next;
boolean palindromeEven = false;
while (rhs != null) {
if (palindromeEven) {
if (rhs.next == null && lhs == null) {
return true;
} else if (rhs.next == null && lhs != null || rhs.next != null && lhs == null) {
return false;
} else if (lhs.val == rhs.next.val) {
lhs = lhs.next;
rhs = rhs.next;
} else {
return false;
}
} else {
if (current.val == rhs.val) {
palindromeEven = true;
} else {
//реверс
if (lhs == null) {
lhs = current;
lhs.next = null;
ListNode tempRhs = new ListNode(rhs.val);
current = tempRhs;
current.next = lhs;
} else {
lhs = current;
ListNode tempRhs = new ListNode(rhs.val);
current = tempRhs;
current.next = lhs;
}
rhs = rhs.next;
}
}
}
return palindromeEven;
}
// нечётный 1-2-2-2-1
private boolean isPalindromeOdd(ListNode head) {
ListNode lhs = null;
ListNode current = head;
ListNode rhs = head.next;
boolean palindromeOdd = false;
while (rhs != null) {
if (palindromeOdd) {
if (rhs.next == null && lhs.next == null) {
return true;
} else if (rhs.next == null && lhs.next != null || rhs.next != null && lhs.next == null) {
return false;
} else if (lhs.next.val == rhs.next.val) {
lhs = lhs.next;
rhs = rhs.next;
} else {
return false;
}
} else {
if (lhs != null && lhs.val == rhs.val) {
palindromeOdd = true;
} else {
//реверс
if (lhs == null) {
lhs = current;
lhs.next = null;
ListNode tempRhs = new ListNode(rhs.val);
current = tempRhs;
current.next = lhs;
} else {
lhs = current;
ListNode tempRhs = new ListNode(rhs.val);
current = tempRhs;
current.next = lhs;
}
rhs = rhs.next;
}
}
}
return palindromeOdd;
}
}