LeetCode 面试题 02.06. 回文链表

一、题目

  编写一个函数，检查输入的链表是否是回文的。

  点击此处跳转题目。

示例 1：

输入： 1->2
输出： false

示例 2：

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

进阶：

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

二、C# 题解

  使用 $O(n)$ 空间很容易写出来，只需要开辟一个数组或者反向链表即可。这里为了实现进阶要求，在原链表上修改。首先将链表的前半部分翻转，然后比较前后两个链表是否相同，最后恢复原链表即可，具体实现细节见代码注释：

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {int n = 0, i;ListNode p = head, q;bool result;// 统计链表长度while (p != null) {p = p.next;n++;}if (n <= 1) return true;    // 长度 <= 1，一定是回文串i = n / 2;                  // 长度的一半，向下取整p = head;while (--i > 0) p = p.next; // 定位到链表中间q = p.next;p.next = null;              // 断开链表Reverse(head);              // 翻转前半部分// 判断链表前后两部分是否相同if (n % 2 == 0) result = Same(p, q);else result = Same(p, q.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next = q;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

  看了一下官方解法，发现还可以进行优化。使用快慢指针定位到中间节点，代码会更加高级和优雅hh。但是效率和上面统计长度然后遍历一半进行定位的方式差不多，因为都是遍历了一个半链表（快指针遍历整个链表，慢指针遍历半个链表），但是快慢指针这种方法它显得高级呀哈哈！

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {if (head == null || head.next == null) return true;ListNode p = head, q = p.next; // p：慢指针，q：快指针bool result;while (q != null && q.next != null) {q = q.next.next;           // q 前进两格if (q != null) p = p.next; // q 不为空，p 才前进}ListNode r = p.next;           // 定位到后半段链表的首部p.next = null;                 // 断开链表Reverse(head);                 // 翻转前半部分// 判断链表前后两部分是否相同if (q != null) result = Same(p, r);else result = Same(p, r.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next = r;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

  修改过后，发现快慢指针跑出来的速度不如直接统计链表长度来得快。果然，高端的代码往往以最朴素的方法写出来~