234. 回文链表

算法分析：

核心：

• 反转链表后半部分，然后和链表前半部分比较

具体方法：

middleNode 

• 慢指针 (slow) 每次前进一步。
• 快指针 (fast) 每次前进两步。

当快指针到达链表末尾时，慢指针正好位于链表的中间节点。

reverseList

• prev   {head.val, null}
• 循环链表：prev{head.next.val, prev}

通过循环，将当前节点的 next 指向 prev，并逐步更新 prev 为当前节点，实现链表的反转。

代码： 

/**
 * 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 ListNode reverseList(ListNode h) {
        if (h == null) {
            return null;
        }
        
        ListNode head = new ListNode(h.val, null); // 正确的构造新节点
        h = h.next; // 先移动 h 指针
        
        while (h != null) { // 正确的循环条件
            head = new ListNode(h.val, head); // 正确的构造新节点
            h = h.next; // 继续遍历
        }
        
        return head;
    }
    
    public ListNode middleNode(ListNode h){
        ListNode middle = h;
        ListNode fast = h;
        while(fast != null && fast.next != null){
            middle = middle.next;
            fast = fast.next.next;
        }
        return middle;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode reverse = reverseList(middleNode(head));
        while(reverse != null){
            if(reverse.val != head.val){
                return false;
            }
            reverse = reverse.next;
            head = head.next; 
        }
        return true;
    }
}

原文地址：https://blog.csdn.net/2301_79140115/article/details/142384475

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