算法初级——判断链表是否回文

判断一个链表是否为回文结构
【题目】 给定一个链表的头节点head,请判断该链表是否为回文结构。 例如: 1->2->1,返回true。 1->2->2->1,返回true。 15->6->15,返回true。 1->2->3,返回false。
进阶: 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)。
/*
* 回文结构判断:
* 1、列表所有元素入栈,然后再依次弹出,弹出的过程与链表每次读取的元素比较,如果全部相同则为回文结构 (空间复杂度为n)
* 2、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指针走到中点,
* 然后将慢指针后面的全部压入栈内,然后依次弹出和从头开始的元素进行比较(空间复杂度为n/2)
* 3、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指针走到中点,
* 然后将慢指针右部分逆序(改指针),然后从两端开始判断是否相等(空间复杂度为1)
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
public class 判断链表是否回文 {
    public static class Node{
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }  
    }
    public static void printLinkedList(Node node) {
        while(node != null) {
            System.out.print(node.value+" ");
            node = node.next;
        }
        System.out.println();
    }
    //空间复杂度为n
    public static boolean isp1(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;   
    }
    //空间复杂度为n/2
    public static boolean isp2(Node head) {
        while(head == null || head.next == null) {
            return true;
        }
        Node slow = head.next;
        Node quick = head;
        while(quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        Stack<Node> stack = new Stack<Node>();
        while(slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        while(!stack.isEmpty()) {
            if(head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;   
    }
    //空间复杂度为1
    public static boolean isp3(Node head) {
        while(head == null || head.next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while(n2.next != null && n2.next.next != null) {
            n1 = n1.next; //中点
            n2 = n2.next.next; //结尾
        }
        //逆序右半部分
        n2 = n1.next; //右半部分第一个节点 head
        n1  = null;  //pre
        Node n3 = null;  //next
        while(n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        //判断是否回文
        n3 = n1;
        n2 = head;
        boolean res = true;
        while(n1 != null && n2 != null) {
            if(n1.value != n2.value) {
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        //还原右半部分的逆序
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }

    public static void main(String[] args) {
        Node head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isp1(head) + " | ");
        System.out.print(isp2(head) + " | ");
        System.out.println(isp3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isp1(head) + " | ");
        System.out.print(isp2(head) + " | ");
        System.out.println(isp3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isp1(head) + " | ");
        System.out.print(isp2(head) + " | ");
        System.out.println(isp3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");
       

    }

}
0 条评论
发表一条评论