题目

Golang 实现【链表反转】如何反转一个单链表。

题目示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

链表结构


type ListNode struct {Val intNext *ListNode
}

第一种实现

解题思路：

利用指针交互的思路

复杂度分析：

时间复杂度 O(N) ：遍历链表使用线性大小时间。

空间复杂度 O(1)：变量 pre 和 cur 使用常数大小额外空间。

func reverseList(cur *ListNode) *ListNode {if cur == nil {return nil}var pre *ListNodefor cur!=nil {//获取下个节点temptemp:=cur.Next//因要翻转，故cur.next=pre 下一个节点等于前一个节点cur.Next=pre//将当前节点赋值给前节点pre=cur//将temp节点赋值给当前节点，用于继续往下执行cur=temp//平行赋值语法  可读性差//cur.Next,pre,cur=pre,cur,cur.Next}return pre
}

第二种实现

解题思路：

利用递归思路实现

复杂度分析：

时间复杂度 O(N)：遍历链表使用线性大小时间。
空间复杂度 O(N)：遍历链表的递归深度达到 NN ，系统使用 O(N)O(N) 大小额外空间。


func reverseListV2(head *ListNode) *ListNode {if head == nil {return nil}//初始时，pre为nilreturn recur(head,nil)
}func recur(cur,pre *ListNode) *ListNode  {//当前cur为nil 说明到了尾节点if cur == nil {return pre}//递归反转，故下个节点，即当前节点，当前节点为前节点res:=recur(cur.Next,cur)//将前节点，赋值给cur.Nextcur.Next=prereturn res
}

Golang解题代码


type ListNode struct {Val intNext *ListNode
}func TestListNode(t *testing.T){head := new(ListNode)head.Val = 1ln2 := new(ListNode)ln2.Val = 2ln3 := new(ListNode)ln3.Val = 3ln4 := new(ListNode)ln4.Val = 4ln5 := new(ListNode)ln5.Val = 5head.Next = ln2ln2.Next = ln3ln3.Next = ln4ln4.Next=ln5//Println(reverseList(head))Println(reverseListV2(head))
}func Println(list *ListNode)  {for list!=nil{fmt.Printf("val:%v ",list.Val)list = list.Next}
}
func reverseList(cur *ListNode) *ListNode {if cur == nil {return nil}var pre *ListNodefor cur!=nil {//获取下个节点temptemp:=cur.Next//因要翻转，故cur.next=pre 下一个节点等于前一个节点cur.Next=pre//将当前节点赋值给前节点pre=cur//将temp节点赋值给当前节点，用于继续往下执行cur=temp//平行赋值语法  可读性差//cur.Next,pre,cur=pre,cur,cur.Next}return pre
}func reverseListV2(head *ListNode) *ListNode {if head == nil {return nil}//初始时，pre为nilreturn recur(head,nil)
}func recur(cur,pre *ListNode) *ListNode  {//当前cur为nil 说明到了尾节点if cur == nil {return pre}//递归反转，故下个节点，即当前节点，当前节点为前节点res:=recur(cur.Next,cur)//将前节点，赋值给cur.Nextcur.Next=prereturn res
}