# LeetCode Solution, Easy, 234. Palindrome Linked List

# [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/)

## 題目敘述

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

**Example 1:**

![pal1linked-list.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1656982501249/1t82ILywt.jpeg align="left")

    Input: head = [1,2,2,1]
    Output: true

**Example 2:**

![pal2linked-list.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1656982498888/rJk8Afyo1.jpeg align="left")

    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?

### 題目翻譯

需要判斷一個連結序列是否是回文的，可以的話讓其空間複雜度是常數。

## 解法解析

解題的方式這邊列出三種想法，第一種用 Two pointer 的方式去做比對、第二種用遞迴的方式找到結尾後再往回推去跟原本的序列做比對、第三種 In place 的方式來達到常數的複雜度。

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

### 解法範例

#### Go

##### Copy into Array List and then Use Two Pointer Technique

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	var (
		vals        []int
		currentNode *ListNode = head
	)
	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

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
var frontPointer *ListNode

func isPalindrome(head *ListNode) bool {
	frontPointer = head
	return recursivelyCheck(head)
}

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

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}

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

	var (
		result         bool      = true
		firstPosition  *ListNode = head
		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
}

func endOfFirstHalf(head *ListNode) *ListNode {
	var (
		slow *ListNode = head
		fast *ListNode = head
	)
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func reverseList(head *ListNode) *ListNode {
	var (
		current  *ListNode = head
		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

```javascript
/**
 * 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) {
    const vals = [];
    let currentNode = head;
    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

```javascript
/**
 * 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 frontPointer = head;
    const recursivelyCheck = (currentNode) => {
        if (currentNode) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (frontPointer.val !== currentNode.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    };
    return recursivelyCheck(head);
};
```

##### Reverse Second Half In-place

```javascript
/**
 * 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) {
    if (!head) return true;

    let firstHalfEnd = endOfFirstHalf(head);
    let secondHalfStart = reverseList(firstHalfEnd.next);

    let result = true;
    let firstPosition = head;
    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) => {
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

const reverseList = (head) => {
    let previous = null;
    let current = head;
    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

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        var vals: MutableList<Int> = mutableListOf()
        var currentNode: ListNode? = head
        while (currentNode != null) {
            vals.add(currentNode.`val`)
            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

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    var frontPointer: ListNode? = null

    fun isPalindrome(head: ListNode?): Boolean {
        frontPointer = head

        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

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        if (head == null) return true

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

        var result: Boolean = true
        var firstPosition: ListNode? = head
        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
    }

    fun endOfFirstHalf(head: ListNode?): ListNode? {
        var fast: ListNode? = head
        var slow: ListNode? = head
        while (fast?.next != null && fast?.next?.next != null) {
            fast = fast.next?.next
            slow = slow?.next
        }
        return slow
    }

    fun reverse(head: ListNode?): ListNode? {
        var previous: ListNode? = null
        var current: ListNode? = head
        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

```php
/**
 * 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
{

    /**
     * @param ListNode $head
     * @return Boolean
     */
    function isPalindrome($head)
    {
        $vals = [];
        $currentNode = $head;
        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

```php
/**
 * 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;

    /**
     * @param ListNode $head
     * @return Boolean
     */
    function isPalindrome($head)
    {
        $this->frontPointer = $head;
        return $this->recursivelyCheck($head);
    }

    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

```php
/**
 * 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
{
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function isPalindrome($head)
    {
        if (is_null($head)) {
            return true;
        }

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

        $result = true;
        $firstPosition = $head;
        $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;
    }

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

    function reverseList($head)
    {
        $prev = null;
        $current = $head;
        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

```python
# 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 = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]
```

##### Recursive

```python
# 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:
        self.front_pointer = head

        def recursively_check(current_node=head):
            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

```python
# 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 head is None:
            return True

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

        # Check whether or not there's a palindrome.
        result = True
        first_position = head
        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

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous
```

#### Rust

```rust
```

#### Swift

##### Copy into Array List and then Use Two Pointer Technique

```swift
/**
 * Definition for singly-linked list.
 * 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]()
        var currentNode: ListNode? = head
        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

```swift
/**
 * Definition for singly-linked list.
 * 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 {
        self.frontPointer = head

        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

```swift
/**
 * Definition for singly-linked list.
 * 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 firstHalfEnd: ListNode? = self.endOfFirstHalf(head)
        var secondHalfStart: ListNode? = self.reverse(firstHalfEnd?.next)

        var result: Bool = true
        var firstPosition: ListNode? = head
        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? {
        var slow = head
        var fast = head
        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
        var current: ListNode? = head
        while current != nil {
            let nextNode = current?.next
            current?.next = previous
            previous = current
            current = nextNode
        }
        return previous
    }
}
```