题解 | #判断一个链表是否为回文结构#

package linkedList;

import java.util.List;
import java.util.Stack;

/**

• @description: 判断一个链表是否是回文 栈方式
• @author: zhangxianglong
• @date: 2021/6/18
• @time: 18:36
• Copyright (C) 2018 Meituan
• All rights reserved
• /

public class Palindrome {

public static void main(String[] args) {

    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(3);
    ListNode node6 = new ListNode(2);
    ListNode node7 = new ListNode(1);

    node1.next = node2;
    node2.next = node3;
    node3.next = node5;
    node5.next = node5;
    node5.next = node6;

// node6.next = node7;

    System.out.println(isPalindrome2(node1));
}

/**
 * 采用stack
 *
 * @param head
 * @return
 */
public static boolean isPalindrome1(ListNode head) {

    //将链表压入栈 
    Stack<Integer> stack = new Stack<>();
    ListNode curr = head;
    while (curr != null) {
        stack.push(curr.val);
        curr = curr.next;
    }
    //  同时遍历原始链表和stack 
    while (head != null && !stack.empty()) {
        if (head.val != stack.pop()) {
            return false;
        }
        head = head.next;
    }
    return true;
}

/**
 * 反转链表的后半部分
 *
 * @param
 * @return
 */

public static boolean isPalindrome2(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    //快慢指针 找到链表的中间结点 half
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    ListNode pre = null;
    ListNode falf = slow;

    //反转后半部分链表
    while (falf != null) {

        ListNode tmp = falf.next;
        falf.next = pre;

        pre = falf;
        falf = tmp;
    }

    //同时遍历原始链表和反转之后的链表 比较是否相等 如果不相等则说明不是回文
    while (pre != null && head != null) {
        if (pre.val != head.val) {
            return Boolean.FALSE;
        }
        pre = pre.next;
        head = head.next;
    }

    return Boolean.TRUE;

}


static class ListNode {
    int val;
    ListNode next = null;

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

}