NOTES · 学习笔记
回文链表
题目
这道题我们依旧可以用栈的思想,先进后出进行解答。
我们看示例: 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
}