leetcode234-回文链表

原题

请判断一个链表是否为回文链表。

示例1:

输入: 1->2
输出: false

示例2:

输入: 1->2->2->1
输出: true

进阶:

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

解法

思想

双指针解法:
一个快指针一个慢指针,快指针每次移两步,慢指针每次移一步,这样快指针的落点有两种情况:

  1. 落在最后一个节点上,此时链表节点为奇数个,慢指针落在中间节点上。
  2. 落在最后一个节点指向的null上,此时链表节点为偶数个,慢指针落在中间靠右第一个节点上。

慢指针将链表分成了两半,将前半部分反转,再与后半部分比较,即可获取结果

leetcode234-回文链表

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) {
        return true;
    }
    ListNode slow = head, fast = head;
    ListNode pre = head, prepre = null;
    while(fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
        pre.next = prepre;
        prepre = pre;
    }
    //链表节点个数为奇数
    if(fast != null) {
        slow = slow.next;
    }
    while(pre != null && slow != null) {
        if(pre.val != slow.val) {
            return false;
        }
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode234-%e5%9b%9e%e6%96%87%e9%93%be%e8%a1%a8/

发表回复

登录后才能评论