This is the 10th day of my participation in Gwen Challenge

234. Palindrome linked list

Topic describes

Determine if a linked list is palindromic.

Example 1:

Input: 1 – > 2

Output: false

Example 2:

Input: 1 – > 2 – > 2 – > 1

Output: true,

link

Leetcode.com/problems/pa…

Thinking analytical

Because it’s a linked list, you can only move through it one by one, so it takes O(n) time to traverse the list and store each node. The space complexity is O(n) because the stack data structure uses the last-in, first-out feature to store data.

Each loop takes the top element of the stack and compares it to the list in order. If not, it means that the list is not a palindrome list. Until the stack is empty.

Algorithm 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) {
         LinkedList<Integer> stack=new LinkedList<>();
         ListNode item=head;
         while(item! =null){
             stack.push(item.val);
             item=item.next;
        }
    
        while(! stack.isEmpty()){if(stack.pop()==head.val){
                
                head=head.next;
            }else{
                return false; }}return true; }}Copy the code

Advanced design

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

The further implementation of O(n) time complexity and O(1) space complexity can be realized by recursive algorithm.

Take the linked list: 1->2->3->4->5->4->3->2->1

Define a ListNode variable ref to point to the first element. Define a recursive loop to be invoked until the last element is reached. During each recursive call, the value of the current element is determined to be equal to the value of the element pointed to by ref. If the same, update ref to point to the next element and continue the recursive call. If not, return false to indicate that the list is not palindromic.

The Code implementation for the Java version is shown below.

/** * 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 {
    ListNode ref;
    public boolean isPalindrome(ListNode head) {
         ref=head;
         return recursive(head);
    }
    public boolean recursive(ListNode head) {
         if(head==null)return true;
         boolean ans=recursive(head.next);
         boolean isEqual = (head.val==ref.val)?true:false;
         ref=ref.next;
         returnans&isEqual; }}Copy the code