# LeetCode Solution, Easy, 234. Palindrome Linked List

## 題目敘述

Given the `head` of a singly linked list, return `true` if it is a palindrome.

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, 10**5]`.
• `0 <= Node.val <= 9`

Follow up: Could you do it in `O(n)` time and `O(1)` space?

## 解法解析

In place 的方式是第一步用龜兔賽法快慢指標的方式找出序列一半的位置，第二步就是將後半部作反轉，第三步就是將其反轉後的部分跟前半做比對。

### 解法範例

#### Go

##### Copy into Array List and then Use Two Pointer Technique
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
var (
vals        []int
)
for currentNode != nil {
vals = append(vals, currentNode.Val)
currentNode = currentNode.Next
}
var (
left  int = 0
right int = len(vals) - 1
)
for ; left < right; left, right = left+1, right-1 {
if vals[left] != vals[right] {
return false
}
}
return true
}
``````
##### Recursive
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
var frontPointer *ListNode

}

func recursivelyCheck(currentNode *ListNode) bool {
if currentNode == nil {
return true
}
if !recursivelyCheck(currentNode.Next) {
return false
}
if frontPointer.Val != currentNode.Val {
return false
}
frontPointer = frontPointer.Next
return true
}
``````
##### Reverse Second Half In-place
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return true
}

var (
secondHalfStart *ListNode = reverseList(firstHalfEnd.Next)
)

var (
result         bool      = true
secondPosition *ListNode = secondHalfStart
)
for result && secondPosition != nil {
if firstPosition.Val != secondPosition.Val {
result = false
}
firstPosition = firstPosition.Next
secondPosition = secondPosition.Next
}
firstHalfEnd.Next = reverseList(secondHalfStart)
return result
}

var (
)
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}

var (
previous *ListNode = nil
)
for current != nil {
nextNode := current.Next
current.Next = previous
previous = current
current = nextNode
}
return previous
}
``````

#### JavaScript

##### Copy into Array List and then Use Two Pointer Technique
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {boolean}
*/
var isPalindrome = function (head) {
const vals = [];
while (currentNode) {
vals.push(currentNode.val);
currentNode = currentNode.next;
}
for (let left = 0, right = vals.length - 1; left < right; left++, right--) {
if (vals[left] !== vals[right]) {
return false;
}
}
return true;
};
``````
##### Recursive
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {boolean}
*/
var isPalindrome = function (head) {
const recursivelyCheck = (currentNode) => {
if (currentNode) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (frontPointer.val !== currentNode.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
};
};
``````
##### Reverse Second Half In-place
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {boolean}
*/
var isPalindrome = function (head) {

let secondHalfStart = reverseList(firstHalfEnd.next);

let result = true;
let secondPosition = secondHalfStart;
while (result && secondPosition) {
if (firstPosition.val !== secondPosition.val) {
result = false;
}
firstPosition = firstPosition.next;
secondPosition = secondPosition.next;
}

firstHalfEnd.next = reverseList(secondHalfStart);
return result;
};

const endOfFirstHalf = (head) => {
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};

const reverseList = (head) => {
let previous = null;
while (current) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
};
``````

#### Kotlin

##### Copy into Array List and then Use Two Pointer Technique
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
var vals: MutableList<Int> = mutableListOf()
while (currentNode != null) {
currentNode = currentNode.next
}

var left: Int = 0
var right: Int = vals.size - 1
while (left < right) {
if (vals[left] != vals[right]) {
return false
}
left++
right--
}
return true
}
}
``````
##### Recursive
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
var frontPointer: ListNode? = null

fun recursivelyCheck(currentNode: ListNode? = head): Boolean {
if (currentNode == null) {
return true
}
if (!recursivelyCheck(currentNode.next)) {
return false
}
if (currentNode.`val` != frontPointer?.`val`) {
return false
}
frontPointer = frontPointer?.next
return true
}

return recursivelyCheck()
}
}
``````
##### Reverse Second Half In-place
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
if (head == null) return true

var secondHalfStart: ListNode? = reverse(firstHalfEnd?.next)

var result: Boolean = true
var secondPosition: ListNode? = secondHalfStart
while (result && secondPosition != null) {
if (firstPosition?.`val` != secondPosition?.`val`) {
result = false
}
firstPosition = firstPosition?.next
secondPosition = secondPosition?.next
}

firstHalfEnd?.next = reverse(secondHalfStart)
return result
}

while (fast?.next != null && fast?.next?.next != null) {
fast = fast.next?.next
slow = slow?.next
}
return slow
}

var previous: ListNode? = null
while (current != null) {
val nextNode = current.next
current.next = previous
previous = current
current = nextNode
}
return previous
}
}
``````

#### PHP

##### Copy into Array List and then Use Two Pointer Technique
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val = 0, \$next = null) {
*         \$this->val = \$val;
*         \$this->next = \$next;
*     }
* }
*/
class Solution
{

/**
* @return Boolean
*/
{
\$vals = [];
while (\$currentNode) {
\$vals[] = \$currentNode->val;
\$currentNode = \$currentNode->next;
}
for (\$left = 0, \$right = count(\$vals) - 1; \$left < \$right; \$left++, \$right--) {
if (\$vals[\$left] != \$vals[\$right]) {
return false;
}
}
return true;
}
}
``````
##### Recursive
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val = 0, \$next = null) {
*         \$this->val = \$val;
*         \$this->next = \$next;
*     }
* }
*/
class Solution
{

private \$frontPointer = null;

/**
* @return Boolean
*/
{
}

function recursivelyCheck(\$currentNode)
{
if (is_null(\$currentNode)) {
return true;
}
if (!\$this->recursivelyCheck(\$currentNode->next) || \$currentNode->val != \$this->frontPointer->val) {
return false;
}
\$this->frontPointer = \$this->frontPointer->next;
return true;
}
}
``````
##### Reverse Second Half In-place
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val = 0, \$next = null) {
*         \$this->val = \$val;
*         \$this->next = \$next;
*     }
* }
*/
class Solution
{
/**
* @return Boolean
*/
{
return true;
}

\$secondHalfStart = \$this->reverseList(\$firstHalfEnd->next);

\$result = true;
\$secondPosition = \$secondHalfStart;
while (\$result && !is_null(\$secondPosition)) {
if (\$firstPosition->val != \$secondPosition->val) {
\$result = false;
}
\$firstPosition = \$firstPosition->next;
\$secondPosition = \$secondPosition->next;
}

\$firstHalfEnd->next = \$this->reverseList(\$secondHalfStart);
return \$result;
}

{
while (!is_null(\$fast->next) && !is_null(\$fast->next->next)) {
\$fast = \$fast->next->next;
\$slow = \$slow->next;
}
return \$slow;
}

{
\$prev = null;
while (\$current) {
\$nextNode = \$current->next;
\$current->next = \$prev;
\$prev = \$current;
\$current = \$nextNode;
}
return \$prev;
}
}
``````

#### Python

##### Copy into Array List and then Use Two Pointer Technique
``````# 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: ListNode | None) -> bool:
vals = []
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]
``````
##### Recursive
``````# 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: ListNode | None) -> bool:

if current_node is not None:
if not recursively_check(current_node.next):
return False
if self.front_pointer.val != current_node.val:
return False
self.front_pointer = self.front_pointer.next
return True

return recursively_check()
``````
##### Reverse Second Half In-place
``````# 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: ListNode | None) -> bool:
return True

# Find the end of first half and reverse second half.
second_half_start = self.reverse_list(first_half_end.next)

# Check whether or not there's a palindrome.
result = True
second_position = second_half_start
while result and second_position is not None:
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next

# Restore the list and return the result.
first_half_end.next = self.reverse_list(second_half_start)
return result

while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow

previous = None
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
``````

#### Rust

``````
``````

#### Swift

##### Copy into Array List and then Use Two Pointer Technique
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func isPalindrome(_ head: ListNode?) -> Bool {
var vals = [Int]()
while currentNode != nil {
vals.append(currentNode!.val)
currentNode = currentNode?.next
}

var left: Int = 0
var right: Int = vals.count - 1
while left < right {
if vals[left] != vals[right] {
return false
}
left += 1
right -= 1
}
return true
}
}
``````
##### Recursive
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
private var frontPointer: ListNode?

func isPalindrome(_ head: ListNode?) -> Bool {

func recursivelyCheck(_ currentNode: ListNode? = head) -> Bool {
if currentNode != nil {
if !recursivelyCheck(currentNode?.next) {
return false
}
if  self.frontPointer!.val != currentNode!.val {
return false
}
self.frontPointer = self.frontPointer?.next
}
return true
}

return recursivelyCheck()
}
}
``````
##### Reverse Second Half In-place
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func isPalindrome(_ head: ListNode?) -> Bool {
guard head != nil else {
return true
}

var secondHalfStart: ListNode? = self.reverse(firstHalfEnd?.next)

var result: Bool = true
var secondPosition: ListNode? = secondHalfStart
while result && secondPosition != nil {
if firstPosition!.val != secondPosition!.val {
result = false
}
firstPosition = firstPosition?.next
secondPosition = secondPosition?.next
}

firstHalfEnd?.next = self.reverse(secondHalfStart)
return result
}

func endOfFirstHalf(_ head: ListNode?) -> ListNode? {
while fast?.next != nil && fast?.next?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}

func reverse(_ head: ListNode?) -> ListNode? {
var previous: ListNode? = nil
while current != nil {
let nextNode = current?.next
current?.next = previous
previous = current
current = nextNode
}
return previous
}
}
``````

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!