LeetCode234-Palindrome Linked List-Easy

判断回文链表

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

LeetCode

解法一：

O(n) time O(1) space

解题步骤：

1. 找到链表中点

2. 把链表从中间切成两个链表

3. 反转后半段链表

4. 比较前后两段链表是否相等

注意：

1）分情况结点个数为偶数or奇数；

2）找链表中间结点、反转链表是基本功，代码要掌握扎实，其他题目也涉及这些基本操作。

3）第四步，两个链表的长度不一定相同。如果原始链表有偶数结点则分成的两半的链表长度相同，奇数则后一半链表比前一半多一个中间结点，但不影响比较结果。

Task 1: 找中间结点：

定义快慢指针，初始化快慢指针（慢指针指向头结点，快指针指向头结点的next结点）。

快指针走两步，慢指针走一步。奇数结点：fast走到null的时候，slow指向中间结点；偶数结点：fast.next == null的时候，slow指向n/2个结点（前一半链表的尾）。

对偶数结点链表来说，退出循环后，通常slow多走一步，使slow指向后一半链表的头。

public LisNode findMiddle(ListNode head) {
    
  if(head == null || head.next == null) {
      return head;
  }

  ListNode slow = head;
  ListNode fast = head.next;

  // Non Pointer Error: while(fast != null || fast.next != null)
  while(fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
  }

  // Non Pinter Error: if(fast.next == null)
  if(fast != null) {
      slow = slow.next;
  }

  return slow;
}

代码：

/**
 * 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.next;
        
        // ERROR: while(fast != null || fast.next != null)
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // ERROR: if(fast.next == null)
        if(fast != null) {
            slow = slow.next;
        }
        
        cutList(head, slow);
        
        return isEqual(head, reverseList(slow));
    }
    
    void cutList(ListNode head, ListNode midHead) {
        while(head.next != midHead) {
            head = head.next;
        }
        head.next = null;
    }
    
    ListNode reverseList(ListNode head){
        
        ListNode revHead = null;
        
        while(head != null) {
            ListNode temp = head.next;
            head.next = revHead;
            revHead = head;
            head = temp;
        }
        
        return revHead;
    }
    
    boolean isEqual(ListNode l1, ListNode l2) {
        
        while(l1 != null && l2 != null) {
            if(l1.val == l2.val) {
                l1 = l1.next;
                l2 = l2.next;
            } else {
                return false;
            }
        }
        
        return true;
    }
}

解法二：如果不考虑空间复杂度O（1），利用“回文链表反转后和原链表相同”的特点。先按顺序把所有的结点值都存入到一个栈 stack 里，然后利用栈的后入先出的特性，就可以按顺序从末尾取出结点值了，此时再从头遍历一遍链表，就可以比较回文的对应位置了，若不同直接返回 false 即可先按顺序把所有的结点值都存入到一个栈 stack 里。

解法二优化：

解法一重复比较一些结点，利用“回文链表前半段和反转后的后半段链表相同”。因为只要前半个链表和后半个链表对应值相等，就是一个回文链表，而并不需要再比较一遍后半个链表，所以我们可以找到链表的中点，这个可以用快慢指针来实现。我们还需要用栈，每次慢指针走一步，都把值存入栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文对应的顺序比较了。