LeetCode-234.回文链表

发表于 分类于

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例1

1
2
输入：head = [1,2,2,1]
输出：true

示例2

1
2
输入：head = [1,2]
输出：false

题解

  1. 双指针法找到链表的中间节点（注意：奇数个节点时fast不为空，fast.next为空，需要将中间节点slow往后移动一位）；
  2. 中间节点开始的后半部分链表反转；
  3. 两个链表的节点一个一个比较节点的val：如果相等就一直后移直到后半部分链表遍历结束，说明是回文链表；如果有不相等的节点值，则不是回文链表，终止循环。
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
/** LeetCode-234.回文链表*/
func isPalindrome(_ head: ListNode?) -> Bool {
  // 找到链表的中间节点（slow）
  var slow = head
  var fast = head?.next
  while(fast !== nil && fast?.next !== nil) {
    slow = slow?.next
    fast = fast?.next?.next
  }
  // 链表个数为奇数个
  if fast !== nil && fast?.next === nil {
    slow = slow?.next
  }
  var isPalindrome = true
  // 重新给fast、slow赋值
  fast = head
  slow = reverseList(slow) // 右半部分链表反转
  // 遍历比较节点值
  while slow !== nil {
    if fast!.val == slow!.val {
      fast = fast?.next
      slow = slow?.next
    } else {
      isPalindrome = false
      break
    }
  }
  return isPalindrome
}
// 反转链表
func reverseList(_ head: ListNode?) -> ListNode? {
  var pre: ListNode? = nil
  var cur: ListNode? = head
  while(cur !== nil) {
      let tmp = cur?.next
      cur?.next = pre
      pre = cur
      cur = tmp
  }
  return pre
}