算法之美（3）判断一个链表是否回文 C++,Go,Rust实现

原创

早起的鸟儿有虫吃

发布于 2025-02-22 11:33:27

6400

代码可运行

文章被收录于专栏：算法之美算法之美

运行总次数：0

代码可运行

题目描述

Palindrome Linked List

来源：https://leetcode.cn/problems/palindrome-linked-list/description/

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

思路分析

我要实现第一个和最后一个元素比较，如何实现
我呀实现第二个和倒数第二个元素比较如果实现。
如果外层的不不配，终止整个比较。

代码实现：

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 从汇编角度解释：c++函数参数传递 引用传递 和指针传递区别？
        // C++ 的语义和安全性，而不是底层实现
        // 隐式地址操作：引用传递隐藏了地址操作的细节，直接使用变量名（value）
        // java golang 等语言将引用传递发挥到极致。
        // ListNode* head：
        // 值传递：传递的是指针的拷贝，函数内部的修改不会影响原始指针。
        // 调用栈：栈帧中存储的是指针的拷贝。
        // ListNode*& frontPointer：
        // 引用传递：传递的是指针的引用，函数内部的修改会直接影响原始指针。
        // 调用栈：栈帧中存储的是对原始指针的引用。
        // void modifyReference(int& ref) {
        //    ref = 10;//*ptr
        //  }
        // modifyReference 函数：
        // mov eax, [esp + 4]：从堆栈中读取第一个参数（value 的地址）。
        // mov dword ptr [eax], 10：通过地址修改 value 的值为 10。
        // ret：返回到调用者。
        // 2个操作  获取 地址 ，获取地址的指向值
        return recursivelyCheck(head, head);
    }
    //
    bool recursivelyCheck(ListNode*& head, ListNode* tail) {
        // 达到某个终止条件
        if (tail == nullptr) {
            return true;
        }
        // 继续递归，判断 递归返回值第二个参数指向下一个元素
        // tail=tail->next
        // head = head
        if (!recursivelyCheck(head, tail->next)) {
            return false;
        }
        // 返回：回溯
        if (head->val != tail->val) {
            return false;
        } else {
            head = head->next;
            return true;
            //int a = 10;
            //int &ref = a;  // ref 是 a 的引用
            //ListNode**head
            //*head=head->next
        }
    }
};

golang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	//phead **ListNode = &head
	return recursivelyCheck(&head, head)

}

// golang二级指针不支持*& Go 语言没有传统的引用类型
// 切片、映射和通道 等类型也表现出类似引用的行为
func recursivelyCheck(phead **ListNode, ptail *ListNode) bool {
	if ptail == nil {
		return true
	}
	//递归
	if !recursivelyCheck(phead, ptail.Next) {
		return false
	}
	//修改二级指针内容
	if (*phead).Val != ptail.Val {
		return false
	}
	*phead = (*phead).Next
	return true
}

引用是多么灵活性了把，通过名字代替*ptr 操作，避免出错，

Rust 这个有点难

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        let mut front = &head;
        Self::recursively_check(&head, &mut front)
    }

    fn recursively_check(
        current: &Option<Box<ListNode>>,
        front: &mut &Option<Box<ListNode>>,
    ) -> bool {
        //if *current == None
        if let Some(node) = current {
            // 递归到链表尾部
            if !Self::recursively_check(&node.next, front) {
                return false;
            }

            // 比较当前节点和前半部分节点的值
            if let Some(f_node) = front.as_ref() {
                if f_node.val != node.val {
                    return false;
                }
                // 移动前半部分指针
                *front = &f_node.next;
            } else {
                return false;
            }
        }
        true
    }
}