单链表反转递归实现 GO语言

链表是一种比较常见的数据结构
单链表的反转用递归实现比较简单，这里简单讲一下。

首先定义节点

type Node struct {
	value int
	next *Node
}

下面是反转递归函数，链表头比较重要，控制链表头不做修改

func reverseList(node *Node) *Node {
	if node.next == nil {//当前节点的下一个节点不存在时，停止递归，返回上层调用
		return node
	} else {
		newHead := reverseList(node.next) //这个位置会一直进入，直到链表到达末尾，然后返回，这就是新链表的表头
		node.next.next = node //这个位置比较难理解，后面举个例子再讲
		node.next = nil
		return newHead
	}
}

举个例子：链表 1->2->3->4->5->6->nil，这是一个链表，链表反转应该是6->5->4->3->2->1->nil，这个大家都懂，调用上面的函数，一直进入递归
假设当前进入的node为5这个节点

//node=5，node.next=6 ,6的next为nil 所以，return 6
//这时再看这3行代码
newHead := 6节点 //6为新的链表头 之后开始反转
node.next.next = node //node.next为6，node.next.next=5,这时候链表已经变成 6->5。
node.next = nil	// 6->5->nil

需要注意的是node.next 不要以为就是newHead，然后还把node.next.next 替换成newHead.next，这是错误的，不然头指针指向的下一个节点一直在被替换。
下面贴上完整的测试用代码：

package main

import "fmt"

type Node struct {
	value int
	next *Node
}

func reverseList(node *Node) *Node {
	if node.next == nil {
		return node
	} else {
		newHead := reverseList(node.next)
		node.next.next = node
		node.next = nil
		return newHead
	}
}

func  main() {
	var number = []int{1,2,3,4,5,6}
	var head *Node

	head = &Node{value:1} //初始化头指针
	current := head		//头指针为了保持不变，赋值给current当前指针
	for i:=1; i<len(number); i++ {
		current.next = &Node{value:number[i]}
		current = current.next	//指针向后移动一位
		current.next = nil
	}
	//这时链表已经串起来了
	//打印一下
	fmt.Printf("正常链表：")
	p := head
	for true {
		if p == nil {
			break
		} else {
			fmt.Printf("%d->", p.value)
			p = p.next
		}
	}
	fmt.Printf("nil\n")

	head = reverseList(head) //链表反转
	//打印一下
	fmt.Printf("反转后的链表：")
	p = head
	for true {
		if p == nil {
			break
		} else {
			fmt.Printf("%d->", p.value)
			p = p.next
		}
	}
	fmt.Printf("nil\n")
}

单链表反转 递归实现 GO语言

单链表反转递归实现 GO语言