leetcode刷题之回文链表

飞熊 • 2023年12月26日下午1:25 • 技术随笔 • 阅读 373

3.判断倒置的后半部分的链表是否等于前半部分的链表

整体代码展示

总结：

这里是题目链接。234. 回文链表 – 力扣（Leetcode）

这道题目的意思是：判断该链表中后半部分倒置是否跟前半部分相同，如果相同就返回true，否则就返回false。

做题思路

1.先用快慢指针来找到该链表的中间节点。

2.倒置后半部分的链表。

3.判断倒置的部分是否跟前半部分相同。

代码实现

1.找到链表的中间节点

使用一个慢指针slow，一次走一步，一个快指针fast，一次走两步。当快指针fast为null或者走到尾节点时，slow所在的节点就是该链表的中间节点。

/**
 * 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) {
        if(head == null) {
            return false;  //判断head是否为空
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时的slow就是链表的中间节点

我们在找到了中间节点后，接下来需要做的就是反转中间节点以后的链表

2.反转中间节点之后的链表

ListNode cur = slow.next;
while(cur != null) {
    ListNode nextNode = cur.next;    //nextNode用来记录cur的下一个节点
    cur.next = slow;  //将cur指向cur的前一个节点
    slow = cur;
    cur = nextNode;
}
//此时slow的位置就是在链表的尾节点处

3.判断倒置的后半部分的链表是否等于前半部分的链表

当链表的节点数为奇数时

当链表的节点数为偶数时

在执行这一步的时候我们需要注意：当链表的节点数为偶数跟奇数的时候，我们需要做出不同的判断来看前半部分的链表跟后半部分的链表是否走完了。

我们假设前半部分是从head1开始走的，后半部分的链表是从head2开始走的。当链表的节点数为奇数的时候，当head1跟head2相遇的时候就说明判断结束了。当链表的节点数为偶数的时候，当

head1.next = head2的时候，我们就可以说判断结束了。

ListNode head1 = head;
ListNode head2 = slow;
while(head1 != head2) {
    if(head1.val != head2.val) {
        return false;
    }
    if(head1.next == head2) {
        return true;
    }
    head1 = head1.next;
    head2 = head2.next;
}
return true;

整体代码展示

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode nextNode = cur.next;
            cur.next = slow;
            slow = cur;
            cur = nextNode;
            }
        while(head != slow ){
            if(head.val != slow.val) {
                return false;
            }
            if(head.next == slow) return true;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}