234.回文链表

题目

请判断一个链表是否为回文链表。

程序核心思想

  • 栈结构 时间O(n) 空间O(n)
    把链表所有的节点入栈,然后遍历一个,出栈一个,如果值都能对上,那么是回文链表。
  • 栈结构 时间O(n) 空间O(n/2)
    先遍历一遍得到节点总数,然后入栈一半的节点,然后遍历剩下的节点,同时出栈,如果值能对上,那么是回文链表。
    先遍历得到节点总数这一步也可以优化,可以通过快慢指针,慢指针走一步,快指针走两步,由此得到链表的中部位置。
  • 不用栈 时间O(n) 空间O(1)
    先用快慢指针,快指针走两步,慢指针走一步,当快指针走完时,慢指针来到中点。然后把后半段逆序,然后通过两个指针,一个从头一个从尾开始遍历,直到中点,如果全部相同则true,否则是false,最后再把逆序的后半段还原回去。

下面的三个代码分别代表了第二和第三种方法,第二种方法写了原始版和快慢指针优化版,第三种方法没有还原回去,还原的方法很简单,题目这部分不检测,我就没写。

Tips

快指针能走两步吗?fast.next != null && fast.next.next != null
用这句话来保证。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.Stack;

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        ListNode a = head;
        int count = 0;
        
        while(a != null){
            a = a.next;
            count++;
        }
        
        a = head;
        for(int i = 0; i < count / 2; i++){
            stack.push(a.val);
            a = a.next;
        }
        
        if(count % 2 != 0){
            a = a.next;
        }
        
        while(!stack.empty()){
            if(a.val != stack.pop()){
                return false;
            }
            a = a.next;
        }
        return true;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.Stack;

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)    return true;
        Stack<Integer> stack = new Stack<Integer>();
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast.next != null  && fast.next.next != null){
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast.next != null){
            stack.push(slow.val);
        }
        slow = slow.next;
        
        
        while(slow != null){
            if(slow.val != stack.pop()){
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.Stack;

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)    return true;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null  && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode b = slow;
        ListNode c = slow;
        if(slow.next != null){
            b = slow.next;
        }else{
            return true;
        }
        if(b.next != null){
            c = b.next;
        }else{
            if(head.val == b.val)   return true;
            return false;
        }
        
        slow.next = null;
        while(c != null){
            b.next = slow;
            slow = b;
            b = c;
            c = c.next;
        }
        b.next = slow;
        
        while(b != null && head != null){
            if(b.val != head.val)   return false;
            b = b.next;
            head = head.next;
        }
        
        return true;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容