234. 回文链表

￡神魔★判官ぃ 2023-03-06 03:39 11阅读 0赞

# 题目： #

[234. 回文链表][234.]  
[判断一个链表是否为回文结构][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：快慢指针 + 反转链表 #

## 1. 题解一：两个while循环 ##

快指针走到末尾，慢指针刚好到中间，其中慢指针将前半部分反转，然后比较反转后的前半部分与原来的后半部分是否相同。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]

## 2. 题解二：三个while循环（首选） ##

*  其一，find mid node：使用快慢指针找到链表中点。
 *  其二，reverse：逆序后半部分。
 *  其三，check：两个指针分别指向链表首尾两端，然后向链表中间进行移动并比较判断是否相同。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
    偶数节点情况：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
    奇数节点情况：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]

# 代码：快慢指针 + 反转链表 #

## 1. 代码一：两个while循环 ##

public class code234 { 
    
        public static boolean isPalindrome(ListNode head) { 
            if(head == null || head.next == null)
            { 
                return true;
            }
            /* 定义快慢两个指针 */
            ListNode slow = head;
            ListNode fast = head;
            /* 虚拟指针 */
            ListNode cur = head;
            ListNode pre = null;
            /* 找中点的时候完成反转 */
            // 快指针走到末尾，慢指针刚好到中间。其中慢指针将前半部分反转。（偶数个链表）
            while(fast != null && fast.next != null)
            { 
                cur = slow;
                slow = slow.next;
                fast = fast.next.next;
                cur.next = pre;
                pre = cur;
            }
            /* 奇数个链表 */
            if(fast != null)
            { 
                slow = slow.next;
            }
            // 然后比较反转后的前半部分与原来的后半部分是否相同
            while(cur != null && slow != null)
            { 
                if(cur.val != slow.val)
                { 
                    return false;
                }
                cur = cur.next;
                slow = slow.next;
            }
            return true;
        }
    
        private static ListNode createLinkedList(int[] arr) { // 将输入的数组输入到链表中
            if (arr.length == 0) { 
                return null;
            }
            ListNode head = new ListNode(arr[0]);
            ListNode current = head;
            for (int i = 1; i < arr.length; i++) { // 过程
                current.next = new ListNode(arr[i]);
                current = current.next;
            }
            return head;
        }
    
        private static void printLinkedList(ListNode head) { // 将链表结果打印
            ListNode current = head;
            while (current != null) { 
                System.out.printf("%d -> ", current.val);
                current = current.next;
            }
            System.out.println("NULL");
        }
    
        public static void main(String[] args) { 
            int[] x = {  1, 2, 2, 1 };
            ListNode list = createLinkedList(x);
            printLinkedList(list);
            boolean res = isPalindrome(list);
            System.out.println(res);
        }
    }

## 2. 代码二：三个while循环（首选） ##

public class code234 { 
    
        public static boolean isPalindrome(ListNode head) { 
            if (head == null) { 
                return true;
            }
            //通过快慢指针找到链表的中间节点
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) { 
                slow = slow.next;
                fast = fast.next.next;
            }
    
            // 反转后半边的链表
            ListNode pre = null;
            while (slow != null) { 
                ListNode temp = slow.next;
                slow.next = pre;
                pre = slow;
                slow = temp;
            }
    
            // 从链表两头到中间，比较两个子链表，判断是相同。（head指向前半链表表头，从前往后遍历；pre指向后半链表表头，从后往前遍历）
            while (head != null && pre != null) { 
                if (head.val != pre.val) { 
                    return false;
                } else { 
                    pre = pre.next;
                    head = head.next;
                }
            }
            return true;
        }
    
        private static ListNode createLinkedList(int[] arr) { // 将输入的数组输入到链表中
            if (arr.length == 0) { 
                return null;
            }
            ListNode head = new ListNode(arr[0]);
            ListNode current = head;
            for (int i = 1; i < arr.length; i++) { // 过程
                current.next = new ListNode(arr[i]);
                current = current.next;
            }
            return head;
        }
    
        private static void printLinkedList(ListNode head) { // 将链表结果打印
            ListNode current = head;
            while (current != null) { 
                System.out.printf("%d -> ", current.val);
                current = current.next;
            }
            System.out.println("NULL");
        }
    
        public static void main(String[] args) { 
            int[] x = { 1, 2, 2, 1};
            ListNode list = createLinkedList(x);
            printLinkedList(list);
            boolean res = isPalindrome(list);
            System.out.println(res);
        }
    }

# 参考： #

1.  [我的快慢指针都从头开始，感觉更好理解][Link 2]
2.  [C++ 使用数组&反转链表][C_]
3.  [234.java 双指针 图解！][234.java _]
4.  [动画演示 234. 回文链表][234. 1]
5.  [【回文链表】两种方法，详细图解][Link 3]
6.  [回文链表][Link 4]
7.  [回文链表（1.栈，2.快慢指针+翻转）][1._2.]
8.  [java，通俗易懂，原地进行，没有额外空间][java]

[234.]: https://leetcode-cn.com/problems/palindrome-linked-list/
[Link 1]: https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230208/c5b4642890b1465b831cf0464d675b50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230208/6ee41fa956c6409eb72c1bbc05f38137.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20230208/50a128f683d5402981070a54b7a1b6a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20230208/2df7d7aee89a4e4ca159715bc4209ff8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20230208/599d7c1ba78f41bd879dafac91be54ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: /images/20230208/cbf40cdcface47f481d380625086da98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: /images/20230208/185020b369944e9e8df6c9790f78af78.png
[Link 2]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/wo-de-kuai-man-zhi-zhen-du-cong-tou-kai-shi-gan-ju/
[C_]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/c-shi-yong-shu-zu-fan-zhuan-lian-biao-by-zuo-10/
[234.java _]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/234java-shuang-zhi-zhen-tu-jie-by-ustcyyw/
[234. 1]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/dong-hua-yan-shi-234-hui-wen-lian-biao-by-user7439/
[Link 3]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-yuan-di-jian-cha-bu-yong-fan-zhu/
[Link 4]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode/
[1._2.]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-1zhan-2kuai-man-zhi-zhen-fan-zhu/
[java]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/javatong-su-yi-dong-yuan-di-jin-xing-mei-you-e-wai/