leetcode234：回文链表

题目链接

leetcode

题目描述

给你一个单链表的头节点 head ，判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现

    为每个结点创建堆栈帧，极大地限制了算法处理链表的大小。
    很多语言中堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000。

    时间复杂度：O(n)
        其中 n 指的是链表的长度。
    空间复杂度：O(n)
        计算机如何运行递归函数，
        在一个函数中调用一个函数时，进入被调用函数之前跟踪它在当前函数中的位置（局部变量等），
        通过运行时存放在堆栈中来实现。
        在堆栈中存放好了数据后，可以进入被调用的函数。
        完成被调用函数之后，会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。
        所以，递归的空间复杂度要考虑堆栈的使用情况。
*/
class Solution_0 {
public:
    ListNode* frontHead;

    bool isPalindrome(ListNode* head) {
        frontHead = head;
        return checkPalindrome(head);
    }

    bool checkPalindrome(ListNode* node) {
        if (node != nullptr) {
            if (!checkPalindrome(node->next)) return false;
            if (node->val != frontHead->val) return false;
            frontHead = frontHead->next;
        }

        return true;
    }
};
/*
    迭代实现，快慢指针

    步骤如下：
        1. 找到链表中前半部分的尾结点
        2. 反转链表的后半部分
        3. 判断该链表是否回文
        4. 还原链表
        5. 返回结果
    
    时间复杂度：O(n)
        其中 n 是链表的长度。
    空间复杂度：O(1)
        只会修改原链表中结点的指向，而在堆栈上的帧不超过 O(1)。
*/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return true;

        // 找到链表中前半部分的尾结点
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 反转链表的后半部分
        slow->next = reverseList(slow->next);

        // 判断该链表是否回文
        slow = slow->next, fast = head;
        while (slow != nullptr) {
            if (slow->val != fast->val) return false;
            slow = slow->next;
            fast = fast->next;
        }

        // 还原链表
        fast->next = reverseList(fast->next);
        return true;
    }

    ListNode* reverseList(ListNode* node) {
        ListNode *prev = nullptr, *cur = node;
        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        
        return prev;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 2, 1};

    // 创建链表
    ListNode* head = createList(nums);
    printList(head);

    // 判断是否为回文链表
    bool result = solution.isPalindrome(head);
    // 打印结果
    cout << "Is Palindrome: " << (result ? "true" : "false") << endl;
    printList(head);

    // 释放内存
    deleteList(head);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：递归实现

    时间复杂度：O(n)
        其中 n 指的是链表的长度。
    空间复杂度：O(n)
        使用递归时空间复杂度要考虑堆栈的使用情况。
*/
func isPalindrome_0(head *ListNode) bool {
    frontPointer := head
    var recursivelyCheck  func(*ListNode) bool

    recursivelyCheck = func(node *ListNode) bool {
        if node != nil {
            if !recursivelyCheck(node.Next) {
                return false
            }
            if node.Val != frontPointer.Val {
                return false
            }
            frontPointer = frontPointer.Next
        }
        return true
    }

    return recursivelyCheck(head)
}

/*
    基本思路：迭代实现
        1.使用快慢指针找到链表的中间节点。
        2.反转链表的后半部分。
        3.比较前半部分和反转后的后半部分是否相同。
    
    时间复杂度：O(n)
        其中 n 是链表的长度。
    空间复杂度：O(1)
        只使用了固定的几个指针。
*/
func isPalindrome(head *ListNode) bool {
    // 快慢指针找到链表中间节点
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 反转链表的后半部分
    reversedHead := reverseList(slow)
    // 比较链表的前半部分和后半部分是否相同
    for head != nil && reversedHead != nil {
        if head.Val != reversedHead.Val {
            return false;
        }
        head = head.Next
        reversedHead = reversedHead.Next
    }

    // 还原链表：再次反转后半部分链表
    slow.Next = reverseList(slow)
    return true
}

func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode = nil, head

    // 当前节点不为空时，进行反转操作
    for cur != nil {
        // 保存下一个节点
        next := cur.Next
        // 将当前节点的 Next 指针指向前一个节点
        cur.Next = prev
        // 更新前一个节点为当前节点
        prev = cur
        // 更新当前节点为下一个节点
        cur = next
    }

    return prev
}

func main() {
    // 测试用例
    testCases := []struct {
        head    []int
        expected bool
    }{
        {
            head:    []int{1, 2, 2, 1},
            expected: true,
        },
        {
            head:    []int{1, 2},
            expected: false,
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.head)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
		result := isPalindrome(head)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}