专栏首页desperate633LintCode 回文链表题目分析代码

LintCode 回文链表题目分析代码

题目

设计一种方式检查一个链表是否为回文链表。

样例 1->2->1 就是一个回文链表。

分析

链表由于其特殊的结构,没法像数组那样判断回文,所以比较原始的方法,先找到链表的中间节点,然后将后半部分反转,然后逐个比较即可。 链表中的算法,通常以寻找链表中间节点,反转链表,合并两个链表这些基本操作构成,所以掌握这些基本操作很重要。 例如本题中寻找链表的中间节点的方法,就是用两个指针一快一慢,一个走两步,一个走一步,快指针先走到底了,这时候慢指针就指向中间节点。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @return a boolean
     */
     public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        
        ListNode middle = findMiddle(head);
        middle.next = reverse(middle.next);
        
        ListNode p1 = head, p2 = middle.next;
        while (p1 != null && p2 != null && p1.val == p2.val) {
            p1 = p1.next;
            p2 = p2.next;
        }
        
        return p2 == null;
    }
    
    private ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        
        return prev;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 19. Remove Nth Node From End of List题目分析代码

    样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

    desperate633
  • LintCode 删除排序链表中的重复数字 II题目分析代码

    给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。 样例 给出 1->2->3->3->4->4->5->null,返回 1->2->5->...

    desperate633
  • LintCode 链表划分题目代码

    样例 给定链表 1->4->3->2->5->2->null,并且 x=3 返回** 1->2->2->4->3->5->null**

    desperate633
  • LeetCode 19. Remove Nth Node From End of List题目分析代码

    样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

    desperate633
  • 有环链表

    一份执着✘
  • 剑指offer 反转链表

    week
  • 数据结构与算法(三)链表

    •插入操作的时候 如果想在角标1添加,要找到角标1的上一个元素。•边界问题 例如首个元素添加 以及最后一个元素添加

    老沙
  • 删除链表中倒数第n个节点

    一份执着✘
  • LeetCode-19 删除链表中的倒数第N个节点

    今天我们学习第19题删除链表中的倒数第N个节点,这是一道中等题。这个题属于面试中的高频题,一定要能手写出来。下面我们看看这道题的题目描述。

    用户3470542
  • [算法总结] 一文搞懂面试链表题

    链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

    尾尾部落

扫码关注云+社区

领取腾讯云代金券