leetcode刷题之回文链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode刷题之回文链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

做题思路

代码实现

1.找到链表的中间节点

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

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

整体代码展示

总结：

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

leetcode刷题之回文链表

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

做题思路

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

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

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

leetcode刷题之回文链表

代码实现

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.反转中间节点之后的链表

leetcode刷题之回文链表

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

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

当链表的节点数为奇数时

leetcode刷题之回文链表

当链表的节点数为偶数时

leetcode刷题之回文链表

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

我们假设前半部分是从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;
    }
}