反转链表的两种解法

反转链表可以用两种方法来实现,一种是常见的迭代法,还有一种方法就是递归,下面来分析一下具体是怎么实现的。
迭代法 思路:
初始化一个变量来存储前驱节点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/...

    推荐阅读