1. 代码段小站首页
  2. 算法

leetcode234-回文链表

彭晨涛 • • 算法 • 阅读 8

原题

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

示例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/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2019年12月15日 18:05
下一篇 2019年12月17日 18:05

相关推荐

发表回复

登录后才能评论