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?

題目翻譯

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

解法解析

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

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

解法範例

Go

Copy into Array List and then Use Two Pointer Technique

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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

# 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

# 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

# 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

Swift

Copy into Array List and then Use Two Pointer Technique

/**
 * 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

/**
 * 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

/**
 * 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
    }
}

LeetCode Solution, Easy, 234. Palindrome Linked List

Comments

LeetCode Solution

LeetCode Solution, Medium, 328. Odd Even Linked List

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

234. Palindrome Linked List

題目敘述

題目翻譯

解法解析

解法範例

Go

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

JavaScript

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Kotlin

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

PHP

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Python

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Rust

Swift

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Command Palette

Comments

LeetCode Solution

LeetCode Solution, Medium, 328. Odd Even Linked List

More from this blog

234. Palindrome Linked List

題目敘述

題目翻譯

解法解析

解法範例

Go

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

JavaScript

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Kotlin

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

PHP

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Python

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place

Rust

Swift

Copy into Array List and then Use Two Pointer Technique

Recursive

Reverse Second Half In-place