算法:链表翻转

public class ListNode {
    
     public var val: Int
     public var next: ListNode?
     public init(_ val: Int) {
         self.val = val
         self.next = nil
     }
}

// 链表对象
class GeneralListNode {

    // 根节点
    var rootNode: ListNode!
    fileprivate var items: Array<Int>
    fileprivate var index = -1
    
    init(items: Array<Int>) {
        self.items = items
        self.rootNode = createList()
    }

    fileprivate func createList() -> ListNode?{
        // 索引加一
        self.index = self.index + 1
        if index < self.items.count && index >= 0 {
            
            let item = self.items[index]
            let node =  ListNode.init(item)
            node.next = createList()  // 递归创建
            return node
        }
        return nil
    }
}

extension GeneralListNode{
    // 递归版本
    class func reverseList(_ head: ListNode?) -> ListNode? {
        
        if head?.next == nil {
            return head
        }
        let newHead = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return newHead
    }
    // while版本 直接原地反转链表
    class func reverseList2(_ head: ListNode?) -> ListNode? {
        
        if head == nil || head?.next == nil {
            return head
        }
        
        var headNode: ListNode? = head
        var newHead: ListNode?
        var preNode:ListNode?

        // 在链表第一个和第二个元素断开链表，保存后半段
        while headNode != nil { // 9 7 6 5 3
            // 保留继续循环的节点
            let tempNode = headNode?.next
            if tempNode == nil { // 最终返回的节点
                newHead = headNode
            }
            headNode?.next = preNode
            preNode = headNode
            headNode = tempNode
        }
        return newHead
    }

    // 打印链表 递归
    func printListNode(node: ListNode?) {
        // 节点为nil,打印"空"
        guard let node = node else {
            return
        }
        if node.next != nil {
            print(node.val, separator: "", terminator: "->")
        } else {
            print(node.val)
        }
        // 递归遍历
        printListNode(node: node.next)
    }
}

/* 以9->7->6->5->3为示例
 let tempNode = 7 6 5 3
 headNode?.next = nil      headNode == 9->nil
 preNode = 9->nil
 headNode = 7 6 5 3
 -------------------
 let tempNode = 6 5 3
 headNode?.next = 9->nil    headNode == 7->9->nil
 preNode = 7->9->nil
 headNode = 6 5 3
 -------------------
 let tempNode = 5 3
 headNode?.next = 7->9->nil  headNode == 6->7->9->nil
 preNode = 6->7->9->nil
 headNode = 5 3
 -------------------
 let tempNode = 3
 headNode?.next = 6->7->9->nil  headNode == 5->6->7->9->nil
 preNode = 5->6->7->9->nil
 headNode = 3
 -------------------
 let tempNode = nil
 newHead = headNode 3
 headNode?.next = preNode   headNode == 3->5->6->7->9->nil
 preNode = headNode 3->5->6->7->9->nil
 headNode = tempNode nil
 */

let items: Array<Int> = [9, 7, 6, 5,  3]
let listNode: GeneralListNode = GeneralListNode(items: items)
listNode.printListNode(node: listNode.rootNode)
print("\n")
let reverseListNode = GeneralListNode.reverseList2(listNode.rootNode)
listNode.printListNode(node: reverseListNode)

9->7->6->5->3
3->5->6->7->9