Skip to content

Latest commit

 

History

History
435 lines (381 loc) · 11 KB

0234.回文链表.md

File metadata and controls

435 lines (381 loc) · 11 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: Optional[ListNode]) -> bool:
        list=[]
        while head: 
            list.append(head.val)
            head=head.next
        l,r=0, len(list)-1
        while l<=r: 
            if list[l]!=list[r]:
                return False
            l+=1
            r-=1
        return True   
      
#反转后半部分链表
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast = slow = head

        # find mid point which including (first) mid point into the first half linked list
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        node = None

        # reverse second half linked list
        while slow:
            slow.next, slow, node = node, slow.next, slow

        # compare reversed and original half; must maintain reversed linked list is shorter than 1st half
        while node:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next
        return True

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
//方法一，使用数组
func isPalindrome(head *ListNode) bool{
    //计算切片长度，避免切片频繁扩容
    cur,ln:=head,0
    for cur!=nil{
        ln++
        cur=cur.Next
    }
    nums:=make([]int,ln)
    index:=0
    for head!=nil{
        nums[index]=head.Val
        index++
        head=head.Next
    }
    //比较回文切片
    for i,j:=0,ln-1;i<=j;i,j=i+1,j-1{
        if nums[i]!=nums[j]{return false}
    }
    return true
}

// 方法二，快慢指针
func isPalindrome(head *ListNode) bool {
    if head==nil&&head.Next==nil{return true}
    //慢指针，找到链表中间分位置，作为分割
    slow:=head
    fast:=head
    //记录慢指针的前一个节点，用来分割链表
    pre:=head
    for fast!=nil && fast.Next!=nil{
        pre=slow
        slow=slow.Next
        fast=fast.Next.Next
    }
    //分割链表
    pre.Next=nil
    //前半部分
    cur1:=head
    //反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
    cur2:=ReverseList(slow)

    //开始两个链表的比较
    for cur1!=nil{
        if cur1.Val!=cur2.Val{return false}
        cur1=cur1.Next
        cur2=cur2.Next
    }
    return true
}
//反转链表
func ReverseList(head *ListNode) *ListNode{
    var pre *ListNode
    cur:=head
    for cur!=nil{
        tmp:=cur.Next
        cur.Next=pre
        pre=cur
        cur=tmp
    }
    return pre
}

JavaScript

var isPalindrome = function(head) {
    const reverseList = head => {// 反转链表
        let temp = null;
        let pre = null;
        while(head != null){
            temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
    // 如果为空或者仅有一个节点，返回true
    if(!head && !head.next) return true;
    let slow = head;
    let fast = head;
    let pre = head;
    while(fast != null && fast.next != null){
        pre = slow; // 记录slow的前一个结点
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null; // 分割两个链表
    // 前半部分
    let cur1 = head;
    // 后半部分。这里使用了反转链表
    let cur2 = reverseList(slow);
    while(cur1 != null){
        if(cur1.val != cur2.val) return false;
        // 注意要移动两个结点
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return true;
};

TypeScript

数组模拟

function isPalindrome(head: ListNode | null): boolean {
    const helperArr: number[] = [];
    let curNode: ListNode | null = head;
    while (curNode !== null) {
        helperArr.push(curNode.val);
        curNode = curNode.next;
    }
    let left: number = 0,
        right: number = helperArr.length - 1;
    while (left < right) {
        if (helperArr[left++] !== helperArr[right--]) return false;
    }
    return true;
};

反转后半部分链表

function isPalindrome(head: ListNode | null): boolean {
    if (head === null || head.next === null) return true;
    let fastNode: ListNode | null = head,
        slowNode: ListNode = head,
        preNode: ListNode = head;
    while (fastNode !== null && fastNode.next !== null) {
        preNode = slowNode;
        slowNode = slowNode.next!;
        fastNode = fastNode.next.next;
    }
    preNode.next = null;
    let cur1: ListNode | null = head;
    let cur2: ListNode | null = reverseList(slowNode);
    while (cur1 !== null) {
        if (cur1.val !== cur2!.val) return false;
        cur1 = cur1.next;
        cur2 = cur2!.next;
    }
    return true;
};
function reverseList(head: ListNode | null): ListNode | null {
    let curNode: ListNode | null = head,
        preNode: ListNode | null = null;
    while (curNode !== null) {
        let tempNode: ListNode | null = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
}