NOTES · 学习笔记
反转链表
题目
看示例,一个链表从开头走到末尾如何反转从末尾走到开头?
我们可以使用栈(stack),栈的特点是先进后出。
我们拿1 -->2 -->3-->nil reverse 3--> 2--> 1-->nil 举例子:
我们把1、2、3放入栈内:
栈顶
↓
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |
+---+取的时候就从栈顶取出,也就是先取出 3,再取出 2,最后取出 1。
这样,使用栈的先进后出就能解决我们这道题。
那么,我们首先定义一个栈,这个栈存储的是链表节点指针,所以用 []*ListNode{} 定义一个空切片,这个切片里面存储的是 *ListNode 类型的元素,也就是链表节点指针。
然后定义一个 curr,让它指向当前头节点。
接着我们将链表的节点依次入栈,入栈后,栈就排成了第一个图示的样子。
我们先取出栈顶的元素,将它作为新的头节点。因为栈顶是最后入栈的节点,所以它就是原链表的最后一个节点。
接着,我们从栈顶往下遍历剩余的节点,依次将当前节点的 Next 指向栈中的下一个节点。
最后,因为原链表的头节点现在变成了最后一个节点,所以需要让它的 Next 指向 nil。
这样就完成了链表的反转。
func reverseList(head *ListNode) *ListNode {
stack :=[]*ListNode{} //定义一个栈,存储链表节点指针
if head ==nil{
return nil //如果刚开始头节点就没有元素,那就直接返回nil
}
curr := head
//我们现在将节点指针入栈
for curr !=nil {
stack=append(stack,curr)
curr=curr.Next
}
//入栈后,我们取出第一个头节点
newHead :=stack[ len(stack)-1 ]
curr = newHead
//接着把剩余的元素取出来
for i := len(stack)-2;i>=0;i--{
curr.Next=stack[i]
curr=curr.Next
}
curr.Next=nil //最后一个节点指向nil
return newHead
}