This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

234. Palindrome Linked List – LeetCode (leetcode-cn.com)

Determine if a linked list is palindromic.

The sample a

Input: 1->2 Output: falseCopy the code

Example 2

Input: 1->2->2->1 Output: trueCopy the code

Tip:

  • The number of nodes in the linked list is within the range [1,105][1, 10^5][1,105]
  • 0 <= Node.val <= 9

Advanced: Can you solve this problem with O(n)O(n)O(n) O(n) time and O(1)O(1)O(1) O(1) space?

Thought analysis

Double pointer method

What’s a palindrome? “Shanghai tap water comes from the sea.”

Era in mandarin that’s primary school, we will how to judge, here come the same as the other way around bai, or from a quotas, from a tail at the end of each step is the same as the results should be, so to this algorithm, we can define two Pointers, a traverse from the very beginning, another since the end of the traversal.

But there’s a problem. Linked lists are usually implemented by linking nodes to each other, so it’s ok to iterate through them from the beginning, but it’s more complicated to do the opposite.

How do you solve that? It’s very easy to iterate over arrays, arrays with double Pointers, all right

So now we have two steps

The first step is to copy the values into the array

The second step, double pointer through the number group to judge

AC code

/** * 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 {
        val vals =  ArrayList<Int> ()var currentNode = head
        while(currentNode ! =null) {
            vals.add(currentNode.`val`) currentNode = currentNode? .next }var head = 0
        var tail = vals.lastIndex
        while(head < tail) {
            if(vals.get(head) ! = vals.get(tail)) {
                return false
            }
            head++
            tail--
        }
        return true}}Copy the code

conclusion

This is the basic solution, there are recursion and fast and slow pointer solution, need to know more.

reference

Palindrome List – Palindrome List – LeetCode (leetcode-cn.com)

My fast and slow Pointers all start from scratch, feel better to understand – Palindrome linked list – LeetCode (leetcode-cn.com)