题目

反转一个单链表。

示例:

输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方案一：

• 迭代：通过while 迭代反转链表

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}
 **/
 func reverseList(_ head:SingNode?) -> SingNode? {
        if head == nil || head?.nextNode == nil {
            return head
        }
        
        var newNode:SingNode? = nil
        var p = head
        while p != nil {
            let temp = p?.nextNode
            p?.nextNode = newNode
            newNode = p
            p = temp
        }
        return newNode
    }

方案二：

• 迭代： 迭代反转链表

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}
 **/
func reverseList(_ head: SingNode?) -> SingNode? {
    if head == nil || head?.next == nil {
        return head
    }

    let newHead = reverseList(head?.next)
    head?.next?.next = head
    head?.next = nil
    return newHead
   }