Swift 反转链表 - LeetCode
LeetCode
题目： 反转链表
反转一个单链表。 示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
方案一：
- 迭代：在链表第一个和第二个元素断开链表，保存后半段，前半段拼在新head前方，然后赋值给新head：具体如下面示意
p: a -> b -> c -> d -> e -> nil
newHead = nil
temp = p.next temp: b -> c -> d -> e -> nil
p.next = newHead p: a -> nil
newHead = p newHead: a -> nil
p = temp p: b -> c -> d -> e -> nil
temp = p.next temp: c -> d -> e -> nil
p.next = newHead p: b -> a -> nil
newHead = p newHead: b -> a -> nil
p = temp p: c -> d -> e -> nil
...
newHead: d -> d -> c -> b -> a -> nil代码一：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var newHead: ListNode? = ListNode.init(0).next
var p = head
while p != nil {
let tmp = p?.next
p?.next = newHead
newHead = p
p = tmp
}
return newHead
}
}方案二：
- 递归：递归找到最后一个节点作为新链表的头节点，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。
1、找到最后一个节点
递归找到newHead
2、反转最后一个节点head?.next.next = head
反转最后一个节点
3、断链 head?.next = nil
断链
4、递归结束
递归结束，完成反转链表
代码二：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
let newHead = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return newHead
}
}举报
腾讯云开发者
