判断一个链表是否为回文结构

一颗蔬菜 2019-09-25 PM 77℃ 0条

【题目】
给定一个链表的头节点head,请判断该链表是否为回文结构。

【解答】
从左至右遍历链表,遍历的过程中把每个节点依次压入栈中。因为栈是先进后出的,所以在遍历完成后,再次出栈时的顺序是和压入的顺序相反的。但是,如果改链表是回文结构,则进站顺序和出栈顺序一致。

【代码实现】

方法1

public boolean is(Node head) {
        int length = 0;
        while (head != null) {
            length ++;
            head = head.next;
        }

        if (length < 2) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        
        for (int i = 0; i < length / 2 - 1; i++) {
            stack.push(head.value);
            head = head.next;
        }

        head = length % 2 != 0 ? head.next : head;

        for (int i = 0; i < length / 2 - 1; i++) {
            if (stack.pop() != head.value) {
                System.out.println(false);
                return false;
            }
            head = head.next;
        }
        return true;
    }

方法2

 public boolean is1(Node head) {

        Stack<Integer> stack = new Stack<Integer>();
        Node cur = head;

        while (cur != null) {
            stack.push(cur.value);
            cur = cur.next;
        }

        while (!stack.isEmpty()) {
            if (stack.pop() != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    
    }
标签: 算法

非特殊说明,本博所有文章均为博主原创。