新题来咯,回文链表
回文链表
力扣题目链接:https://leetcode-cn.com/problems/palindrome-linked-list/
请判断一个链表是否为回文链表。
示例 1:
- 输入: 1->2
- 输出: false
示例 2:
- 输入: 1->2->2->1
- 输出: true
思路
数组模拟
最直接的想法,就是把链表装成数组,然后再判断是否回文。
代码也比较简单。如下:
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
- vector<int> vec;
- ListNode* cur = head;
- while (cur) {
- vec.push_back(cur->val);
- cur = cur->next;
- }
- // 比较数组回文
- for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
- if (vec[i] != vec[j]) return false;
- }
- return true;
- }
- };
上面代码可以在优化,就是先求出链表长度,然后给定vector的初始长度,这样避免vector每次添加节点重新开辟空间
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
-
- ListNode* cur = head;
- int length = 0;
- while (cur) {
- length++;
- cur = cur->next;
- }
- vector<int> vec(length, 0); // 给定vector的初始长度,这样避免vector每次添加节点重新开辟空间
- cur = head;
- int index = 0;
- while (cur) {
- vec[index++] = cur->val;
- cur = cur->next;
- }
- // 比较数组回文
- for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
- if (vec[i] != vec[j]) return false;
- }
- return true;
- }
- };
反转后半部分链表
分为如下几步:
- 用快慢指针,快指针有两步,慢指针走一步,快指针遇到终止位置时,慢指针就在链表中间位置
- 同时用pre记录慢指针指向节点的前一个节点,用来分割链表
- 将链表分为前后均等两部分,如果链表长度是奇数,那么后半部分多一个节点
- 将后半部分反转 ,得cur2,前半部分为cur1
- 按照cur1的长度,一次比较cur1和cur2的节点数值
如图所示:
代码如下:
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
- if (head == nullptr || head->next == nullptr) return true;
- ListNode* slow = head; // 慢指针,找到链表中间分位置,作为分割
- ListNode* fast = head;
- ListNode* pre = head; // 记录慢指针的前一个节点,用来分割链表
- while (fast && fast->next) {
- pre = slow;
- slow = slow->next;
- fast = fast->next->next;
- }
- pre->next = nullptr; // 分割链表
-
- ListNode* cur1 = head; // 前半部分
- ListNode* cur2 = reverseList(slow); // 反转后半部分,总链表长度如果是奇数,cur2比cur1多一个节点
-
- // 开始两个链表的比较
- while (cur1) {
- if (cur1->val != cur2->val) return false;
- cur1 = cur1->next;
- cur2 = cur2->next;
- }
- return true;
- }
- // 反转链表
- ListNode* reverseList(ListNode* head) {
- ListNode* temp; // 保存cur的下一个节点
- ListNode* cur = head;
- ListNode* pre = nullptr;
- while(cur) {
- temp = cur->next; // 保存一下 cur的下一个节点,因为接下来要改变cur->next
- cur->next = pre; // 翻转操作
- // 更新pre 和 cur指针
- pre = cur;
- cur = temp;
- }
- return pre;
- }
- };
其他语言版本
Java
- // 方法一,使用数组
- class Solution {
- public boolean isPalindrome(ListNode head) {
- int len = 0;
- // 统计链表长度
- ListNode cur = head;
- while (cur != null) {
- len++;
- cur = cur.next;
- }
- cur = head;
- int[] res = new int[len];
- // 将元素加到数组之中
- for (int i = 0; i < res.length; i++){
- res[i] = cur.val;
- cur = cur.next;
- }
- // 比较回文
- for (int i = 0, j = len - 1; i < j; i++, j--){
- if (res[i] != res[j]){
- return false;
- }
- }
- return true;
- }
- }
-
- // 方法二,快慢指针
- class Solution {
- public boolean isPalindrome(ListNode head) {
- // 如果为空或者仅有一个节点,返回true
- if (head == null && head.next == null) return true;
- ListNode slow = head;
- ListNode fast = head;
- ListNode pre = head;
- while (fast != null && fast.next != null){
- pre = slow; // 记录slow的前一个结点
- slow = slow.next;
- fast = fast.next.next;
- }
- pre.next = null; // 分割两个链表
-
- // 前半部分
- ListNode cur1 = head;
- // 后半部分。这里使用了反转链表
- ListNode cur2 = reverseList(slow);
-
- while (cur1 != null){
- if (cur1.val != cur2.val) return false;
-
- // 注意要移动两个结点
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return true;
- }
- ListNode reverseList(ListNode head){
- // 反转链表
- ListNode tmp = null;
- ListNode pre = null;
- while (head != null){
- tmp = head.next;
- head.next = pre;
- pre = head;
- head = tmp;
- }
- return pre;
- }
- }
Python
- #数组模拟
- class Solution:
- def isPalindrome(self, head: ListNode) -> bool:
- length = 0
- tmp = head
- while tmp: #求链表长度
- length += 1
- tmp = tmp.next
-
- result = [0] * length
- tmp = head
- index = 0
- while tmp: #链表元素加入数组
- result[index] = tmp.val
- index += 1
- tmp = tmp.next
-
- i, j = 0, length - 1
- while i < j: # 判断回文
- if result[i] != result[j]:
- return False
- i += 1
- j -= 1
- return True
-
- #反转后半部分链表
- class Solution:
- def isPalindrome(self, head: ListNode) -> bool:
- if head == None or head.next == None:
- return True
- slow, fast = head, head
- while fast and fast.next:
- pre = slow
- slow = slow.next
- fast = fast.next.next
-
- pre.next = None # 分割链表
- cur1 = head # 前半部分
- cur2 = self.reverseList(slow) # 反转后半部分,总链表长度如果是奇数,cur2比cur1多一个节点
- while cur1:
- if cur1.val != cur2.val:
- return False
- cur1 = cur1.next
- cur2 = cur2.next
- return True
-
- def reverseList(self, head: ListNode) -> ListNode:
- cur = head
- pre = None
- while(cur!=None):
- temp = cur.next # 保存一下cur的下一个节点
- cur.next = pre # 反转
- pre = cur
- cur = temp
- return pre