Stack
Recursion
Linked List
Two Pointers
Description
Given the head
of a singly linked list, return true
if it is a palindrome or false
otherwise .
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
The number of nodes in the list is in the range [1, 105 ]
.
0 <= Node.val <= 9
Follow up: Could you do it in O(n)
time and O(1)
space?
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution :
def isPalindrome ( self , head : Optional [ ListNode ]) -> bool :
slow , fast = head , head . next
while fast and fast . next :
slow , fast = slow . next , fast . next . next
pre , cur = None , slow . next
while cur :
t = cur . next
cur . next = pre
pre , cur = cur , t
while pre :
if pre . val != head . val :
return False
pre , head = pre . next , head . next
return True
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 /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome ( ListNode head ) {
ListNode slow = head ;
ListNode fast = head . next ;
while ( fast != null && fast . next != null ) {
slow = slow . next ;
fast = fast . next . next ;
}
ListNode cur = slow . next ;
slow . next = null ;
ListNode pre = null ;
while ( cur != null ) {
ListNode t = cur . next ;
cur . next = pre ;
pre = cur ;
cur = t ;
}
while ( pre != null ) {
if ( pre . val != head . val ) {
return false ;
}
pre = pre . next ;
head = head . next ;
}
return true ;
}
}
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 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public :
bool isPalindrome ( ListNode * head ) {
ListNode * slow = head ;
ListNode * fast = head -> next ;
while ( fast && fast -> next ) {
slow = slow -> next ;
fast = fast -> next -> next ;
}
ListNode * pre = nullptr ;
ListNode * cur = slow -> next ;
while ( cur ) {
ListNode * t = cur -> next ;
cur -> next = pre ;
pre = cur ;
cur = t ;
}
while ( pre ) {
if ( pre -> val != head -> val ) return false ;
pre = pre -> next ;
head = head -> next ;
}
return true ;
}
};
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 /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome ( head * ListNode ) bool {
slow , fast := head , head . Next
for fast != nil && fast . Next != nil {
slow , fast = slow . Next , fast . Next . Next
}
var pre * ListNode
cur := slow . Next
for cur != nil {
t := cur . Next
cur . Next = pre
pre = cur
cur = t
}
for pre != nil {
if pre . Val != head . Val {
return false
}
pre , head = pre . Next , head . Next
}
return true
}
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 /**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function isPalindrome ( head : ListNode | null ) : boolean {
let slow : ListNode = head ,
fast : ListNode = head . next ;
while ( fast != null && fast . next != null ) {
slow = slow . next ;
fast = fast . next . next ;
}
let cur : ListNode = slow . next ;
slow . next = null ;
let prev : ListNode = null ;
while ( cur != null ) {
let t : ListNode = cur . next ;
cur . next = prev ;
prev = cur ;
cur = t ;
}
while ( prev != null ) {
if ( prev . val != head . val ) return false ;
prev = prev . next ;
head = head . next ;
}
return true ;
}
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 /**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function ( head ) {
let slow = head ;
let fast = head . next ;
while ( fast && fast . next ) {
slow = slow . next ;
fast = fast . next . next ;
}
let cur = slow . next ;
slow . next = null ;
let pre = null ;
while ( cur ) {
let t = cur . next ;
cur . next = pre ;
pre = cur ;
cur = t ;
}
while ( pre ) {
if ( pre . val !== head . val ) {
return false ;
}
pre = pre . next ;
head = head . next ;
}
return true ;
};
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 /**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public bool IsPalindrome ( ListNode head ) {
ListNode slow = head ;
ListNode fast = head . next ;
while ( fast != null && fast . next != null ) {
slow = slow . next ;
fast = fast . next . next ;
}
ListNode cur = slow . next ;
slow . next = null ;
ListNode pre = null ;
while ( cur != null ) {
ListNode t = cur . next ;
cur . next = pre ;
pre = cur ;
cur = t ;
}
while ( pre != null ) {
if ( pre . val != head . val ) {
return false ;
}
pre = pre . next ;
head = head . next ;
}
return true ;
}
}
GitHub