数据结构与算法——Java实现 15.习题——判断回文链表

目录

234. 回文链表

方法1

思路

方法2

思路

---

毕竟，明天又是新的一天

                        —— 24.9.24

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

        如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

方法1

思路

找到链表的中间结点，对后半链表进行反转，如果反转后的后半链表与前半链表相等，则链表为回文链表

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode newHead = reverse(mid);
//        System.out.println(newHead);

        while (newHead != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }

    private ListNode reverse(ListNode old1) {
        // 反转链表
        ListNode new1 = null;
        while (old1 != null){
            ListNode old2 = old1.next;
            old1.next = new1;
            new1 = old1;
            old1 = old2;
        }
        return new1;
    }

    private ListNode middleNode(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        // 快慢指针找中间结点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

方法2

思路

省去一层循环，将反转和找中间结点的两个循环放在一起，缩减为一次循环

① 找中间点的同时反转前半个链表

② 反转后的前半个链表 与 中间点开始的后半个链表，逐一比较

    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode new1 = null;
        ListNode old1 = head;
        ListNode mid;
        if (head == null || head.next == null){
            mid = head;
        } else {// 快慢指针找中间结点
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;

                // 反转链表
                ListNode old2 = old1.next;
                old1.next = new1;
                new1 = old1;
                old1 = old2;
            }
        }

        if (fast != null){
            slow = slow.next;
        }

        while (new1 != null) {
            if (new1.val != slow.val) {
                return false;
            }
            new1 = new1.next;
            slow = slow.next;
        }
        return true;
    }

原文地址：https://blog.csdn.net/m0_73983707/article/details/142462825

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！