Skip to content

Latest commit

 

History

History
296 lines (247 loc) · 8.22 KB

0234.回文链表.md

File metadata and controls

296 lines (247 loc) · 8.22 KB
Raw

欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

234.回文链表

力扣题目链接

请判断一个链表是否为回文链表。

示例 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

Go



JavaScript