LeetCode
反转一个单链表。 示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
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
}
}
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
}
}