Shulou(Shulou.com)06/01 Report--

This article is about how LeetCode judges palindromes. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic description:

Please determine whether a linked list is a palindromic linked list.

Example 1:

Input: 1-> 2 output: false

Example 2:

Input: 1-> 2-> 2-> 1 output: true

Thought analysis: iterative method:

The way to avoid using O (n) O (n) extra space is to change the input.

We can reverse the first (second) part of the linked list (modify the structure of the linked list), and then compare the first half with the second half. After the comparison, we should restore the linked list to its original state. Although it does not require recovery to pass the test case, people who use this function usually do not want the linked list structure to be changed.

Although this method can reduce the space complexity to O (1) O (1), it also has some disadvantages in concurrent environment. In a concurrent environment, the function needs to lock the access of other threads or processes to the linked list because the linked list will be modified during function execution.

The whole process can be divided into the following steps:

Find the tail node of the front (back) half of the linked list.

Reverse (front) the back half of the linked list.

Judge whether palindromes or not.

Python implements # Definition for singly-linked list.

# class ListNode:

# def _ _ init__ (self, x):

# self.val = x

# self.next = None

Class Solution:

Def isPalindrome (self, head):

"

: type head: ListNode

: rtype: bool

"

If head is None or head.next is None:

Return True

If head.next.next is None:

Return head.val = = head.next.val

Fast = slow = Q = head

While fast.next and fast.next.next:#, the interpretation condition of fast pointer here is a little different from that of judgment ring.

Fast = fast.next.next

Slow = slow.next

Def reverse_list (head):

If head is None:

Return head

Cur = head

Pre = None

Nxt = cur.next

While nxt:

Cur.next = pre

Pre = cur

Cur = nxt

Nxt = nxt.next

Cur.next = pre

Return cur

P = reverse_list (slow.next)

While p.next:

If p.val! = q.val:

Return False

P = p.next

Q = q.next

Return p.val = = q.val

Java implementation: / * *

* Definition for singly-linked list.

* public class ListNode {

* int val

* ListNode next

* ListNode () {}

* ListNode (int val) {this.val = val;}

* ListNode (int val, ListNode next) {this.val = val; this.next = next;}

*}

, /

Class Solution {

Public boolean isPalindrome (ListNode head) {

If (head = = null | | head.next = = null) {

Return true

}

ListNode slow=head

ListNode fast=head

ListNode pre=null,prepre=null

/ / reverse the first half pointer

While (fastening boxes, null boxes, fast.nextboxes) {

Pre=slow

Slow=slow.next

Fast=fast.next.next

Pre.next=prepre

Prepre=pre

}

If (fast! = null) {

Slow = slow.next

}

/ / compare whether some pointers are the same before and after

While (predominantly null) {

If (pre.valedicate.val) {

Return false

}

Pre=pre.next

Slow=slow.next

}

Return true

}

}

Recursive method:

The currentNode pointer is a first-to-tail node, which is compared from back to front because of the recursive nature. FrontPointer is a pointer outside a recursive function. Returns false if currentNode.val! = frontPointer.val. Instead, frontPointer moves forward and returns true.

The correctness of the algorithm is that the order of recursive processing nodes is opposite, and we record another variable outside the function, so in essence, we match both forward and reverse iterations.

The so-called recursion means passing it down from the top down and then coming back from the bottom up.

Java implementation code: class Solution {

Private ListNode frontPointer

Private boolean recursivelyCheck (ListNode currentNode) {

If (currentNode! = null) {

If (! recursivelyCheck (currentNode.next)) {

Return false

}

If (currentNode.val! = frontPointer.val) {

Return false

}

FrontPointer = frontPointer.next

}

Return true

}

Public boolean isPalindrome (ListNode head) {

FrontPointer = head

Return recursivelyCheck (head)

}

Thank you for reading! This is the end of the article on "how to judge the palindrome linked list by LeetCode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.