Leetcode No.234

Create@2023/06/08 21:08:13 | Update@2023/06/09 08:59:04Tags: leetcode, linked-list, palindrome, list-reverse

leetcode #234 题解

234

快慢指针找到中间位置
- 分析题意: 回文串是正着反着读都完全一致的字符串
- 由于链表无法随机访问，因此通过倒置后半部分链表与前半部分链表比较来操作会快一些
- 慢指针一次前进一个结点，快指针一次前进两个结点，最终慢指针会指向中间结点
倒置链表
- 声明: 链表分割为3部分：已转置的链表、将要转置的结点和未转置的链表
- 初始化:
  - head指针指向已转置链表的头结点
  - tail指针指向已转置的链表的尾结点
  - next指针总是指向将要转置的结点，即tail结点的下一个结点，next = tail.next
- 循环:
  - 接续: 先将tail指针指向未转置链表的头结点，即tail.next = next.next；特殊地：当未转置链表为空时，即next指针已是未转置链表的最后一个结点时，tail指针将指向空，即tail.next = null
  - 前插: 将next指针指向已转置链表的头结点，即next.next = head
  - 更新: 将next指针设置为已转置链表的头结点，即head = next