给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
反转链表示例.jpg
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
摘一个示例做个说明.
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
条件分析:
- 单链表头节点 -> 需要从头节点开始反转
解决思路1:
- 根据分析1,采用迭代方式进行反转
先定义返回的空链表和循环链表(需要反转的链表).然后当循环链表不空的时候进行循环(即链表没有到尾节点),定义临时变量为循环链表的next,然后让循环链表的next指向返回链表.返回的链表为循环链表.然后循环链表为临时链表(即下一个节点后的链表)
func reverseList(_ head: ListNode?) -> ListNode? {
// 返回链表
var newHead: ListNode? = nil
// 循环节点
var old = head
while old != nil {
// 先定义临时变量存储next
let tmp = old?.next
// 节点指向返回链表(定义新链表承接)
old?.next = newHead
// 返回链表等于循环链表
newHead = old
// 让循环链表为临时变量,进行继续循环
old = tmp
}
return newHead
}
解决思路2:
- 根据分析1,采用递归方式进行反转
先判断链表是否为空或者单节点链表,是则直接返回(也用以结束递归).然后开始递归节点,直到尾节点结束递归.然后从尾部开始反转链表节点.直到头节点.然后置空头节点的next即可.
func reverseList(_ head: ListNode?) -> ListNode? {
// 单链表和空链表直接返回
if head == nil || head?.next == nil{
return head
}
// 递归调用,直到尾节点
let node : ListNode? = reverseList(head?.next)
// 直接反转链表节点指向
head?.next?.next = head
// 最后next置空
head?.next = nil
return node
}
测试用例:
let endNode = ListNode.init(0)
let fourNode = ListNode.init(1)
fourNode.next = endNode
let threeNode = ListNode.init(2)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(4)
firstNode.next = secondNode
let headNode = ListNode.init(5)
headNode.next = firstNode
考察要点:
- 递归
- 链表
