给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:输入:head = [] 输出:[]
提示:
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
解题思路
GO链表
先是递归,递归比较好写。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head==nil||head.Next==nil{
return head
}
newHead:=reverseList(head.Next)
head.Next.Next=head
head.Next=nil
return newHead
}
然后是迭代。迭代写的不够多反而没有递归熟。多练吧。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head==nil||head.Next==nil{
return head
}
cur:=head
var newHead *ListNode
for cur!=nil{
tmp:=cur.Next
//nil-1-2-3-nil
cur.Next=newHead
newHead=cur
cur=tmp
}
return newHead
}