算法系列-力扣234-回文链表判定

回文链表判定

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

方法一：栈反转对比法

解题思路：找到中间节点后用栈辅助反转对比
解题方法：
找到链表的中间节点并判断奇数还是偶数
头结点到中间节点前的节点入栈，偶数从中间节点开始和栈内元素进行比较；
奇数从中间节点后面的节点开始和栈内元素进行比较；
若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）
时间复杂度：O(n)
空间复杂度：O(n)

import java.util.List;
import java.util.Stack;

import javax.management.ListenerNotFoundException;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
       public static boolean isPalindrome(ListNode head) {
        /**
         * head -> 1 -> 2 -> 2 -> 1 -> null
         * head -> 1 -> 2 -> 1 -> null
         * 找到链表的中间节点并判断奇数还是偶数
         * 头结点到中间节点的节点入栈，偶数从中间节点开始和栈内元素进行比较；
         * 奇数从中间节点后面的节点开始和栈内元素进行比较；
         * 若比较到最后一个节点都相当该链表为回文链表（栈空或比较到最后一个节点）
         */
        if(head == null){
            return false;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next=head;
        ListNode slow=dummy;
        ListNode fast=dummy;
        ListNode midNode=null;
        Boolean isEvent=true;
        while (fast.next!=null){
            slow=slow.next;
            if(fast.next.next!=null) {
                fast = fast.next.next;
            } else{
                fast=fast.next;
                isEvent=false;
            }
        }
        midNode = isEvent ? slow.next : slow;
        Stack stack=new Stack<>();
        ListNode p=dummy.next;
        while(p!=midNode){
            stack.push(p);
            p=p.next;
        }
        
        ListNode m=isEvent?midNode:midNode.next;
        while(m!=null){
            ListNode tmp=stack.pop();
            if(m.val!=tmp.val){
                return false;
            }
            m=m.next;
        }
        
        return true;
        
    }
}
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

方法二：链自反转对比法

解题思路：找到中间节点后用栈辅助反转对比
解题方法：
找到链表的中间节点并判断奇数还是偶数
继续利用双指针反转中间节点前的链表。
偶数从中间节点开始和反转链进行比较；
奇数从中间节点后面的节点开始和反转链进行比较；
若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）
时间复杂度：O(n)
空间复杂度：O(1)

   public static boolean isPalindrome(ListNode head) {
        /**
         * [1,0,1]
         * head -> 1 -> 2 -> 2 -> 1 -> null
         * head -> 1 -> 2 -> 1 -> null
             找到链表的中间节点并判断奇数还是偶数
             继续利用头插法反转中间节点前的链表。
             偶数从中间节点开始和反转链进行比较；
             奇数从中间节点后面的节点开始和反转链进行比较；
             若比较到最后一个节点都相等该链表为回文链表（栈空或比较到最后一个节点）
         */
        if(head == null){
            return false;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next=head;
        ListNode slow=dummy;
        ListNode fast=dummy;
        ListNode midNode=null;
        Boolean isEvent=true;
        while (fast.next!=null){
            slow=slow.next;
            if(fast.next.next!=null) {
                fast = fast.next.next;
            } else{
                fast=fast.next;
                isEvent=false;
            }
        }
        midNode = isEvent ? slow.next : slow;


        ListNode p = head;
        head=null;
        while (p!=midNode){
            ListNode tmp=p.next;
            p.next=head;
            head=p;
            p=tmp;
        }

        //偶数从中间节点开始和反转链进行比较
        ListNode m = isEvent ? midNode : midNode.next;

        boolean isPalindrome=true;
        p=head;
        while (isPalindrome && p!=null){
            if(p.val!=m.val){
                isPalindrome=false;
            }
            p=p.next;
            m=m.next;
        }

        // 还原链表
        p = head;
        head=midNode;
        while (p!=null){
            ListNode tmp=p.next;
            p.next=head;
            head=p;
            p=tmp;
        }

        return  isPalindrome;
    }
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