题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

样例

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

算法1

(迭代) $O(n)$

时间复杂度

参考文献

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
}

a := head
b := a.Next
var c *ListNode

for b != nil {
    c = b.Next
    b.Next = a
    a = b
    b = c
}
head.Next = nil

return a

}

算法2

(递归) $O(n)$

时间复杂度

参考文献

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
}

tail := reverseList(head.Next)

a := head
b := head.Next

b.Next = a
a.Next = nil

return tail

}