回文链表

发表于 | 分类于 |
字数统计: 760 字 | 阅读时长 ≈ 3 分钟

**题目描述：**编写一个函数，检查输入的链表是否是回文的。

示例 1：
输入： 1->2
输出： false

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isPalindrome(ListNode head) {

  }
}

思路

本题同时考察了寻找链表中间节点、链表反转、判断两链表是否相同的知识点，把它们拆开来，就很好做了

  1. 采用快慢两个指针去寻找链表的中间节点；
  2. 根据链表的中间节点反转后一半的链表；
  3. 迭代比较链表前一半的元素和后一半的元素，判断节点的值是否相等，得出是否为回文
链表回文奇数.jpeg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
  public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) return true;
    ListNode midNode = findMidNode(head); // 找中间节点
    ListNode secondLinkHead = reverseLinked(midNode.next); // 反转后半部分的链表

    /* 判断两链表是否相同的知识点 */
    boolean res = true;
    ListNode cur1 = head, cur2 = secondLinkHead;
    while(res && cur2 != null) { // 已右边链表为主，一是cur2.next是有可能为空的，二是当奇数个时刚好不检测中间的节点
      if(cur1.val != cur2.val) res = false;
      cur1 = cur1.next;
      cur2 = cur2.next;
    }
    return res;
  }

  /* 快慢指针寻找中间节点 */
  private ListNode findMidNode(ListNode head) {
    ListNode fast = head, slow = head;
    while(fast.next != null && fast.next.next != null) { // 注意这个判断条件，当链表为偶数，slow指向两个中间数的第一个
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

  /* 反转链表 */
  private ListNode reverseLinked(ListNode node) {
    ListNode cur = node, pre = null;
    while(cur != null) {
      ListNode temp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = temp;
    }
    return pre;
  }
}

var isPalindrome = function(head) {
  if(head === null || head.next === null) return true;
  // 找中间节点
  let midNode = findMidNode(head);

  // 反转后半部分的节点
  let secondLinkHead = reverseLink(midNode.next);

  // 判断前后链表是否相同
  let res = true;
  let cur1 = head, cur2 = secondLinkHead;
  // 以右边链表为主，一是cur2.next是有可能为空的，二是当奇数个时刚好不检测中间的节点
  while(res && cur2 != null) {
    if(cur1.val !== cur2.val) return false;
    cur1 = cur1.next;
    cur2 = cur2.next;
  }  
  return res;
};

var findMidNode = function(head) {
  let slow = head, fast = head;
  // 如果返回第二个中间节点，判断则为 fast && fast.next
  // 偶数个时，返回第一个中间结点
  while(fast.next  && fast.next.next ) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

var reverseLink = function(head) {
  let pre = null, cur = head;
  while(cur !== null) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  return pre;
}

复杂度分析：

  • 时间复杂度：O(n)，其中 n 指的是链表的大小。
  • 空间复杂度：O(1)，我们是一个接着一个的改变指针，我们在堆栈上的堆栈帧不超过 O(1)。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了99.93%的用户

  • 内存消耗：42.4 MB, 在所有 Java 提交中击败了55.30%的用户