共计 897 个字符,预计需要花费 3 分钟才能阅读完成。
反转链表能够用两种办法来实现,一种是常见的迭代法,还有一种办法就是递归,上面来剖析一下具体是怎么实现的。
迭代法
思路:
初始化一个变量来存储前驱节点 pre,从头节点开始遍历链表,每遍历一个节点,就将该节点的后驱节点指向 pre,实现了反转,而后更新 pre 的值为以后节点以便下一个节点的应用,遍历完当前以前的尾节点就是新的头节点。
func (head *Node) reverse() *Node {
if head == nil {return nil}
var reverseHead *Node // 反转后单链表的头结点
var preNode *Node
curNode := head
for curNode != nil {
nextNode := curNode.next
if nextNode == nil {reverseHead = curNode // 尾结点转换为头结点}
// 反转实现,以后结点的前驱结点变成后驱结点
curNode.next = preNode
// 设置下一个结点的前驱结点
preNode = curNode
curNode = nextNode
}
return reverseHead
}
递归法
思路
递归的办法会一直压栈,反转 (head.Next) 的前提是反转(head.Next.Next), 始终到终止条件 head.Next == nil 时拿到尾节点的值才真正开始解决,last 节点的变动如下:
6
6->5
6->5->4
6->5->4->3
6->5->4->3->2
6->5->4->3->2->1
假如 reverse(head.Next)返回的曾经是反转后的节点 last,当初还须要做的就是将 2 号节点的后驱节点指向 head,以及原 head 节点的后驱节点指向 nil,一个节点的 case 想明确了,其余的其实就是一样的过程了。
func reverse(head *Node) *Node {
if head == nil || head.Next == nil {return head}
last := reverse(head.Next)
head.Next.Next = head
head.Next = nil
return last
}
参考资料:https://labuladong.github.io/…
正文完