NOTES · 学习笔记

反转链表

LeetCode链表 · 简单约 3 分钟

题目

看示例,一个链表从开头走到末尾如何反转从末尾走到开头?

我们可以使用栈(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

}