LeetCode-234-回文链表

回文链表

题目描述:请判断一个链表是否为回文链表。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:链表遍历

首先,如果head为空或者只有一个节点,直接返回true。

当head大于1个节点时,首先遍历链表,用count记录链表节点的个数为count,然后将链表的前count/2个放入一个栈中,然后将链表中的后一半节点和栈中的元素进行比较,如果有不同的,则返回false。如果都相同,最后返回true。

import java.util.Stack;

public class LeetCode_234 {
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode cur = head;
        // 链表节点的个数
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        // 将前面的一半节点放入栈中
        Stack temp = new Stack<>();
        ListNode newCur = head;
        for (int i = 1; i <= count / 2; i++) {
            temp.push(newCur.val);
            newCur = newCur.next;
        }
        int start;
        if (count % 2 == 0) {
            start = count / 2 + 1;
        } else {
            start = count / 2 + 2;
            newCur = newCur.next;
        }
        for (int i = start; i <= count; i++) {
            if (temp.pop() != newCur.val) {
                return false;
            }
            newCur = newCur.next;
        }

        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(0);
        head.next.next = new ListNode(1);

        System.out.println(isPalindrome(head));
    }
}
【每日寄语】 为别人鼓掌的人也是在给自己的生命加油。

你可能感兴趣的