Palindrome Linked List-LeetCode#234

234. Palindrome Linked List

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

回文链表
给出一个单链表,判断它是否是回文。
思路:定义两个链表,为 temp 与 rate。temp 每次走一步,rate 每次走两步,当 rate 走完的时候,temp 刚好到中间位置。用 Stack 记录 temp 每次走的 val 值,然后 temp 继续走完,每次与 Stack 栈顶的值比较。

public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode temp = head;
    ListNode rate = head;
    Stack<Integer> stack = new Stack<>();
    stack.push(head.val);
    while (rate.next != null && rate.next.next != null) {
        temp = temp.next;
        rate = rate.next.next;
        stack.push(temp.val);
    }
    if (rate.next == null) stack.pop();
    while (temp.next != null){
        temp = temp.next;
        if (temp.val != stack.peek()){
            return false;
        }
        stack.pop();
    }
    return true;
}
文章已创建 108

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部