NOTES · 学习笔记

回文链表

LeetCode链表 · 简单约 3 分钟

题目

这道题我们依旧可以用栈的思想,先进后出进行解答。

我们看示例: 1 --> 2 --> 2 -->1 return true。

那么我们可以先将链表每个节点指针放入栈中 [1-->2-->2-->1]

然后我们通过从栈顶开始,逐个取出节点的值,和原链表的节点值进行比较。如果每个节点的值都相同,那么就说明这是一个回文链表,返回 true;如果有一个不相同,就返回 false。

我们首先定义一个栈保存这个链表,如果头节点为空的话,那么永远返回真。

然后我们将链表入栈,通过 curr = curr.Next(这个是将当前所指链表元素移动到下一个节点,目的是为了将每个链表节点都能入栈) 不断移动指针,直到链表遍历结束。

入栈完成后,我们将 curr 重新指向头节点,然后从栈顶开始,逐个比较栈中的节点值和原链表的节点值。

如果发现有一个节点值不相同,就返回 false。如果全部比较完成,就返回 true。

func isPalindrome(head *ListNode) bool {
    stack := []*ListNode{} //创建一个栈,用来保存链表指针
    if head ==nil{
        return true   //永远为真
    }
    curr := head
    for curr !=nil{
        stack=append(stack,curr) //将链表入栈
        curr=curr.Next   //更新头指针
    }
    //入栈后,判断栈内链表和初始链表是否回文
    curr=head   //这里将current重新放在最初的头指针,进行比较
    for i:=len(stack)-1;i>=0;i--{
        if curr.Val !=stack[i].Val{
            return false
        }
        curr=curr.Next //每进行一次都要更新curr位置,确保每个链表值都被比较到
    }
    return true

}