Skip to content

Commit 69cc60f

Browse files
yanglbmeyanglbme
committed
feat: add python and java solutions to leetcode problem: No.234
添加LeetCode题解：234. 回文链表
1 parent 265bb28 commit 69cc60f

File tree

4 files changed

+238
-31
lines changed

4 files changed

+238
-31
lines changed

‎solution/0200-0299/0234.Palindrome Linked List/README.md

Lines changed: 85 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,14 +32,98 @@
3232
<!-- 这里可写当前语言的特殊实现逻辑 -->
3333

3434
```python
35+
# Definition for singly-linked list.
36+
# class ListNode:
37+
# def __init__(self, x):
38+
# self.val = x
39+
# self.next = None
40+
41+
class Solution:
42+
def isPalindrome(self, head: ListNode) -> bool:
43+
if not head:
44+
return True
45+
mid = self.find_mid_node(head)
46+
second_half_list = self.reverse_list(mid.next)
47+
result = True
48+
p, q = head, second_half_list
49+
while result and q:
50+
if p.val != q.val:
51+
result = False
52+
else:
53+
p, q = p.next, q.next
54+
mid.next = self.reverse_list(second_half_list)
55+
return result
56+
57+
def reverse_list(self, head):
58+
pre, p = None, head
59+
while p:
60+
q = p.next
61+
p.next = pre
62+
pre = p
63+
p = q
64+
return pre
65+
66+
def find_mid_node(self, head):
67+
slow = fast = head
68+
while fast.next and fast.next.next:
69+
slow, fast = slow.next, fast.next.next
70+
return slow
3571

3672
```
3773

3874
### **Java**
3975
<!-- 这里可写当前语言的特殊实现逻辑 -->
4076

4177
```java
42-
78+
/**
79+
* Definition for singly-linked list.
80+
* public class ListNode {
81+
* int val;
82+
* ListNode next;
83+
* ListNode(int x) { val = x; }
84+
* }
85+
*/
86+
class Solution {
87+
public boolean isPalindrome(ListNode head) {
88+
if (head == null) {
89+
return true;
90+
}
91+
ListNode mid = findMidNode(head);
92+
ListNode secondHalfList = reverseList(mid.next);
93+
boolean result = true;
94+
ListNode p = head, q = secondHalfList;
95+
while (result && q != null) {
96+
if (p.val != q.val) {
97+
result = false;
98+
} else {
99+
p = p.next;
100+
q = q.next;
101+
}
102+
}
103+
mid.next = reverseList(secondHalfList);
104+
return result;
105+
}
106+
107+
private ListNode reverseList(ListNode head) {
108+
ListNode pre = null, p = head;
109+
while (p != null) {
110+
ListNode q = p.next;
111+
p.next = pre;
112+
pre = p;
113+
p = q;
114+
}
115+
return pre;
116+
}
117+
118+
private ListNode findMidNode(ListNode head) {
119+
ListNode slow = head, fast = head;
120+
while (fast.next != null && fast.next.next != null) {
121+
slow = slow.next;
122+
fast = fast.next.next;
123+
}
124+
return slow;
125+
}
126+
}
43127
```
44128

45129
### **...**

‎solution/0200-0299/0234.Palindrome Linked List/README_EN.md

Lines changed: 85 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,6 @@
3636
Could you do it in O(n) time and O(1) space?</p>
3737

3838

39-
40-
4139
## Solutions
4240

4341

@@ -46,13 +44,97 @@ Could you do it in O(n) time and O(1) space?</p>
4644
### **Python3**
4745

4846
```python
47+
# Definition for singly-linked list.
48+
# class ListNode:
49+
# def __init__(self, x):
50+
# self.val = x
51+
# self.next = None
52+
53+
class Solution:
54+
def isPalindrome(self, head: ListNode) -> bool:
55+
if not head:
56+
return True
57+
mid = self.find_mid_node(head)
58+
second_half_list = self.reverse_list(mid.next)
59+
result = True
60+
p, q = head, second_half_list
61+
while result and q:
62+
if p.val != q.val:
63+
result = False
64+
else:
65+
p, q = p.next, q.next
66+
mid.next = self.reverse_list(second_half_list)
67+
return result
68+
69+
def reverse_list(self, head):
70+
pre, p = None, head
71+
while p:
72+
q = p.next
73+
p.next = pre
74+
pre = p
75+
p = q
76+
return pre
77+
78+
def find_mid_node(self, head):
79+
slow = fast = head
80+
while fast.next and fast.next.next:
81+
slow, fast = slow.next, fast.next.next
82+
return slow
4983

5084
```
5185

5286
### **Java**
5387

5488
```java
55-
89+
/**
90+
* Definition for singly-linked list.
91+
* public class ListNode {
92+
* int val;
93+
* ListNode next;
94+
* ListNode(int x) { val = x; }
95+
* }
96+
*/
97+
class Solution {
98+
public boolean isPalindrome(ListNode head) {
99+
if (head == null) {
100+
return true;
101+
}
102+
ListNode mid = findMidNode(head);
103+
ListNode secondHalfList = reverseList(mid.next);
104+
boolean result = true;
105+
ListNode p = head, q = secondHalfList;
106+
while (result && q != null) {
107+
if (p.val != q.val) {
108+
result = false;
109+
} else {
110+
p = p.next;
111+
q = q.next;
112+
}
113+
}
114+
mid.next = reverseList(secondHalfList);
115+
return result;
116+
}
117+
118+
private ListNode reverseList(ListNode head) {
119+
ListNode pre = null, p = head;
120+
while (p != null) {
121+
ListNode q = p.next;
122+
p.next = pre;
123+
pre = p;
124+
p = q;
125+
}
126+
return pre;
127+
}
128+
129+
private ListNode findMidNode(ListNode head) {
130+
ListNode slow = head, fast = head;
131+
while (fast.next != null && fast.next.next != null) {
132+
slow = slow.next;
133+
fast = fast.next.next;
134+
}
135+
return slow;
136+
}
137+
}
56138
```
57139

58140
### **...**

‎solution/0200-0299/0234.Palindrome Linked List/Solution.java

Lines changed: 32 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -8,37 +8,42 @@
88
*/
99
class Solution {
1010
public boolean isPalindrome(ListNode head) {
11-
if (head == null || head.next == null) {
11+
if (head == null) {
1212
return true;
1313
}
14-
ListNode slow = head;
15-
ListNode fast = head;
16-
while (fast != null && fast.next != null) {
17-
slow = slow.next;
18-
fast = fast.next.next;
19-
}
20-
if (fast != null) {
21-
slow = slow.next;
14+
ListNode mid = findMidNode(head);
15+
ListNode secondHalfList = reverseList(mid.next);
16+
boolean result = true;
17+
ListNode p = head, q = secondHalfList;
18+
while (result && q != null) {
19+
if (p.val != q.val) {
20+
result = false;
21+
} else {
22+
p = p.next;
23+
q = q.next;
24+
}
2225
}
23-
24-
ListNode rightPre = new ListNode(-1);
25-
while (slow != null) {
26-
ListNode t = slow.next;
27-
slow.next = rightPre.next;
28-
rightPre.next = slow;
29-
slow = t;
26+
mid.next = reverseList(secondHalfList);
27+
return result;
28+
}
29+
30+
private ListNode reverseList(ListNode head) {
31+
ListNode pre = null, p = head;
32+
while (p != null) {
33+
ListNode q = p.next;
34+
p.next = pre;
35+
pre = p;
36+
p = q;
3037
}
31-
32-
ListNode p1 = rightPre.next;
33-
ListNode p2 = head;
34-
while (p1 != null) {
35-
if (p1.val != p2.val) {
36-
return false;
37-
}
38-
p1 = p1.next;
39-
p2 = p2.next;
38+
return pre;
39+
}
40+
41+
private ListNode findMidNode(ListNode head) {
42+
ListNode slow = head, fast = head;
43+
while (fast.next != null && fast.next.next != null) {
44+
slow = slow.next;
45+
fast = fast.next.next;
4046
}
41-
return true;
42-
47+
return slow;
4348
}
4449
}

‎solution/0200-0299/0234.Palindrome Linked List/Solution.py

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
# Definition for singly-linked list.
2+
# class ListNode:
3+
# def __init__(self, x):
4+
# self.val = x
5+
# self.next = None
6+
7+
class Solution:
8+
def isPalindrome(self, head: ListNode) -> bool:
9+
if not head:
10+
return True
11+
mid = self.find_mid_node(head)
12+
second_half_list = self.reverse_list(mid.next)
13+
result = True
14+
p, q = head, second_half_list
15+
while result and q:
16+
if p.val != q.val:
17+
result = False
18+
else:
19+
p, q = p.next, q.next
20+
mid.next = self.reverse_list(second_half_list)
21+
return result
22+
23+
def reverse_list(self, head):
24+
pre, p = None, head
25+
while p:
26+
q = p.next
27+
p.next = pre
28+
pre = p
29+
p = q
30+
return pre
31+
32+
def find_mid_node(self, head):
33+
slow = fast = head
34+
while fast.next and fast.next.next:
35+
slow, fast = slow.next, fast.next.next
36+
return slow

0 commit comments

Comments
 (0)