【算法100天 | 18】回文链表的多种解法（JAVA实现）

淩亂°似流年 2023-09-24 14:14 19阅读 0赞

### 回文链表 Leetcode 234（简单） ###

给你一个单链表的头节点 `head` ，请你判断该链表是否为回文链表。如果是，返回 `true` ；否则，返回 `false` 。  
![在这里插入图片描述][a3d4b9fd5f6f44f09656703fc3f156fe.png]

**节点Node类：**

public class Node {
        
        public int value;
        public Node next;
    
        public Node(int v) {
        
            value = v;
        }
    }

#### 方法一：使用容器1 ####

遍历一遍链表使用栈保存链表数据，再遍历一遍链表，出栈数据和链表数据对比，到栈为空时，出栈数据都和链表数据相等，则为回文。

**空间复杂度：O(n)，时间复杂度：O(2n)**

##### 代码 #####

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

#### 方法二：使用容器2 ####

遍历一遍链表找到中节点，再从中节点开始遍历链表的后半段，使用栈保存链表后半段数据；  
再遍历一半链表，出栈数据和链表数据对比，到栈为空时，出栈数据都和链表数据相等，则为回文。

**空间复杂度：O(n / 2)，时间复杂度：O(2n)**

##### 代码 #####

public static boolean isPalindrome2(Node head) {
        
        if (head == null || head.next == null) {
        
            return true;
        }
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
        
            slow = slow.next;
            fast = fast.next.next;
        }
    
        Stack<Node> stack = new Stack<>();
        while (slow != null) {
        
            stack.push(slow);
            slow = slow.next;
        }
    
        while (!stack.empty()) {
        
            if (head.value != stack.pop().value) {
        
                return false;
            }
            head = head.next;
        }
        return true;
    }

#### 方法三：修改原链表 ####

*  从链表的中点（上中点`<链表有偶数个节点时>`）之后开始反转后半段的链表，记录下两段链表的起点；
    
     *  如果链表的节点有偶数个：则链表上中点（两个中节点的前一个）的next为null。
     *  否者，链表中点的next为null。
 *  遍历两段链表：
    
     *  对比同样位置的节点值，直到有一段链表的next为null；
 *  最后要把链表调整回原样。

**空间复杂度：O(1)，时间复杂度：O(2.5 \* n)**

##### 代码 #####

public static boolean isPalindrome3(Node head) {
        
        if (head == null || head.next == null) {
        
            return true;
        }
        /**
         * 1）反转链表中节点之后的链表段
         */
        // n1 -> mid node
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) {
        
            n1 = n1.next;
            n2 = n2.next.next;
        }
        // n3 -> right part first node
        Node n3 = n1.next;
        n1.next = null;
        while (n3 != null) {
        
            // n2 -> save next node
            n2 = n3.next;
            // reverse
            n3.next = n1;
            n1 = n3;
            n3 = n2;
        }
    
        // n2 / n1 -> save last node （reversed first node）
        n2 = n1;
        // n3 -> left first node
        n3 = head;
    
        /**
         * 2）对比中节点之前的正常链表段 和 中节点之后反转的链表段。
         */
        boolean res = true;
        while (n1 != null && n3 != null) {
        
            if (n1.value != n3.value) {
        
                res = false;
                break;
            }
            n1 = n1.next;
            n3 = n3.next;
        }
    
        /**
         * 3）还原head链表
         */
        // n1 -> last node 's next node
        n1 = n2.next;
        // last node 'next to null
        n2.next = null;
        while (n1 != null) {
        
            // n3 -> temp node for store "next" node
            n3 = n1.next;
            n1.next = n2;
            // finally, n2 is mid
            n2 = n1;
            // finally, n1 / n3 is null
            n1 = n3;
        }
        return res;
    }

##### 执行耗时 #####

![在这里插入图片描述][0377059b112d4c8787606201b1b6a08c.png]

[a3d4b9fd5f6f44f09656703fc3f156fe.png]: https://img-blog.csdnimg.cn/a3d4b9fd5f6f44f09656703fc3f156fe.png
[0377059b112d4c8787606201b1b6a08c.png]: https://img-blog.csdnimg.cn/0377059b112d4c8787606201b1b6a08c.png