Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 234. Palindrome Linked List

回文連結序列

攻城獅's photo
攻城獅
Jul 5, 2022
Play this article

234. Palindrome Linked List

題目敘述

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

Example 1:

pal1linked-list.jpeg

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

Example 2:

pal2linked-list.jpeg

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

Did you find this article valuable?

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

leetcodelearningProgramming BlogsGeneral Programminglearn coding