Fork me on GitHub

Reverse Linked List

题目介绍

LeetCode 206. Reverse Linked List,反转链表,迭代法和递归法同时实现。

解题思路

迭代法

迭代的精髓在于按顺序对指针指向的扭转。以1->2->3->4为例,当迭代到第三次时,前面的运算已经保存了一个pre值,值为2->1,这时到3这个节点,只需把它的指向指到pre即可,而构成的新的链表3->2->1保存为pre以供下次迭代,但是因为它后面的值还要做运算,所以把它原先的指向先保存起来(为next),为了下次继续迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var headNode = head
var pre: ListNode? = nil
while (headNode != nil) {
let tmp = headNode?.next
headNode?.next = pre
pre = headNode
headNode = tmp
}
return pre
}
}

递归法

递归的精髓在于将next当做参数传入reverseList函数时,在下一次递归中对参数的操作,会反应在上次的参数值上。
还是以1->2->3->4举例子,4次递归后(回溯前),其实是将引用链全部打破:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
let next = head?.next
head?.next = nil
let newHead = reverseList(next)
next?.next = head
return newHead
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/11/06/ReverseLinkedList/