題目描述

給定一個鏈表的頭節(jié)點head，請判斷該鏈表是否為回 文結(jié)構(gòu)。 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。

解題思路

將鏈表的節(jié)點裝入棧中，然后重鏈表頭結(jié)點遍歷和出棧節(jié)點匹配 如果有一個不同則不是回文結(jié)構(gòu)，否則就是。

代碼實現(xiàn)

import java.util.Stack;
/**
 * 判斷一個鏈表是否為回文結(jié)構(gòu) 【題目】 給定一個鏈表的頭節(jié)點head，請判斷該鏈表是否為回 文結(jié)構(gòu)。 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。
進階： 如果鏈表長度為N，時間復(fù)雜度達到O(N)，額外空間復(fù)雜 度達到O(1)。
 * @author Administrator
 *
 */
public class Code_11_IsPalindromeList {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    // need n extra space
    public static boolean isPalindrome1(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    
    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        Node head = null;
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);


    }

}