NC78 反转链表
链表，最基础的数据结构，非连续、非顺序存储结构。
单向链表反转的解法一般有两种：
解法一：递归
func ReverseList ( _ head: ListNode?) -> ListNode? {
// 结束条件：当前节点为空或下一节点为空，则当前已到达链表尾部
if head == nil || head?.next == nil {
return head
}
// 递归至链表末尾
let result = ReverseList(head?.next)
// 将当前节点下一节点的的下一节点置为当前节点
// 当前节点的下一节点置为空
// 反转完成
head?.next?.next = head
head?.next = nil
return result
}
解法二：迭代
func ReverseList ( _ head: ListNode?) -> ListNode? {
// 声明reversed用于指向反转后的节点
var reversed: ListNode?
var current = head
while current != nil {
// 临时保存当前节点的下一节点
let next = current?.next
// 将当前节点下一节点指向结果
current?.next = reversed
// 结果指向当前节点
reversed = current
// 当前节点指向下一节点
current = next
}
return reversed
}
