234.回文链表

LeetCode LeetCode 双指针 链表 栈 递归
发布时间 :
字数:1.5k 阅读 : 评论:
  1. 234.回文链表
    1. 234.1 题目
    2. 234.2 题解
      1. List辅助双指针
      2. 反转后半部分链表
    3. 234.3 代码
    4. 234.4 运行结果

234.回文链表

234.1 题目

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

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围 [1, 10^5] 内
  • 0 <= Node.val <= 9

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

234.2 题解

List辅助双指针

// 方法一：List辅助双指针
// 把链表各个节点的值存到List中双指针前后夹击判断
static bool IsPalindrome1(ListNode head)
{
    // 创建一个整数列表用于存储链表节点的值
    List<int> list = new List<int>();

    // 用于迭代链表的当前节点
    ListNode currentNode = head;
    
    // 遍历链表，将节点的值添加到列表中
    while (currentNode != null)
    {
        list.Add(currentNode.val);
        currentNode = currentNode.next;
    }

    // 使用双指针，分别指向列表的开头和结尾
    int left = 0;
    int right = list.Count - 1;

    // 检查是否为回文，比较列表两端的值
    while (left < right)
    {
        // 如果相等，继续向中间移动指针
        if (list[left] == list[right])
        {
            left++;
            right--;
        }
        else
        {
            // 如果不相等，表示不是回文，返回 false
            return false;
        }
    }

    // 如果所有比较都相等，说明是回文，返回 true
    return true;
}

反转后半部分链表

// 方法二：反转后半部分链表
// 快慢指针找到中间节点，反转后半节点进行对比
static bool IsPalindrome2(ListNode head)
{
    // 特殊情况：空链表或只有一个节点的链表视为回文
    if (head == null || head.next == null)
    {
        return true;
    }

    // 使用快慢指针找到链表中点
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 反转后半部分链表
    ListNode secondHalf = ReverseLinkedList(slow.next);

    // 比较前半部分和反转后的后半部分链表
    while (secondHalf != null)
    {
        // 如果值不相等，表示不是回文，返回 false
        if (head.val != secondHalf.val)
        {
            return false;
        }
        
        // 向后移动指针
        head = head.next;
        secondHalf = secondHalf.next;
    }

    // 如果所有比较都相等，说明是回文，返回 true
    return true;
}

// 反转链表
static ListNode ReverseLinkedList(ListNode head)
{
    // 用于存储反转后的链表头部和每一次迭代的当前节点的前一节点
    ListNode prev = null;

    // 遍历原始链表
    while (head != null)
    {
        // 保存下一个节点的引用
        ListNode next = head.next;

        // 反转当前节点的指针指向前一节点
        head.next = prev;
        
        // 更新prev为当前节点
        prev = head;
        // 将head移动到下一个节点
        head = next;
    }

    // 返回反转后的链表头部
    return prev;
}

234.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 1：
        // 输入：head = [1,2,2,1]
        // 输出：true

        // 示例 2：
        // 输入：head = [1,2]
        // 输出：false

        // 提示：
        // 链表中节点数目在范围[1, 105] 内
        // 0 <= Node.val <= 9

        // 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

        #endregion

        #region 测试

        // 示例 1
        ListNode head1 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
        bool result1 = IsPalindrome1(head1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = IsPalindrome2(head1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        ListNode head2 = new ListNode(1, new ListNode(2));
        bool result2 = IsPalindrome1(head2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = IsPalindrome2(head2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：List辅助双指针
    // 把链表各个节点的值存到List中双指针前后夹击判断
    static bool IsPalindrome1(ListNode head)
    {
        // 创建一个整数列表用于存储链表节点的值
        List<int> list = new List<int>();

        // 用于迭代链表的当前节点
        ListNode currentNode = head;
        
        // 遍历链表，将节点的值添加到列表中
        while (currentNode != null)
        {
            list.Add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针，分别指向列表的开头和结尾
        int left = 0;
        int right = list.Count - 1;

        // 检查是否为回文，比较列表两端的值
        while (left < right)
        {
            // 如果相等，继续向中间移动指针
            if (list[left] == list[right])
            {
                left++;
                right--;
            }
            else
            {
                // 如果不相等，表示不是回文，返回 false
                return false;
            }
        }

        // 如果所有比较都相等，说明是回文，返回 true
        return true;
    }

    // 方法二：反转后半部分链表
    // 快慢指针找到中间节点，反转后半节点进行对比
    static bool IsPalindrome2(ListNode head)
    {
        // 特殊情况：空链表或只有一个节点的链表视为回文
        if (head == null || head.next == null)
        {
            return true;
        }

        // 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转后半部分链表
        ListNode secondHalf = ReverseLinkedList(slow.next);

        // 比较前半部分和反转后的后半部分链表
        while (secondHalf != null)
        {
            // 如果值不相等，表示不是回文，返回 false
            if (head.val != secondHalf.val)
            {
                return false;
            }
            
            // 向后移动指针
            head = head.next;
            secondHalf = secondHalf.next;
        }

        // 如果所有比较都相等，说明是回文，返回 true
        return true;
    }

    // 反转链表
    static ListNode ReverseLinkedList(ListNode head)
    {
        // 用于存储反转后的链表头部和每一次迭代的当前节点的前一节点
        ListNode prev = null;

        // 遍历原始链表
        while (head != null)
        {
            // 保存下一个节点的引用
            ListNode next = head.next;

            // 反转当前节点的指针指向前一节点
            head.next = prev;
            
            // 更新prev为当前节点
            prev = head;
            // 将head移动到下一个节点
            head = next;
        }

        // 返回反转后的链表头部
        return prev;
    }


    #endregion
}

// 链表节点定义
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

234.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏