单向链表

链表就是一串节点，每个Node中有两个关键参数
1、节点Node的值，value
2、持有的下一个Node的引用，nil表示链表最后一个Node
如创建一个基本的Node类，并重写description

public class FMNode<T> {
    public var val:T
    var nextNode:FMNode?
    init(val:T,nextNode:FMNode? = nil) {
        self.val = val
        self.nextNode = nextNode
    }
    
}
extension FMNode:CustomStringConvertible{
    public var description: String{
        guard let nextNode = nextNode else {
            return "\(val)"
        }
        return "\(val) -> " + String(describing: nextNode)
    }
}

如果我们要使用该节点，则需要用ListNode来管理这些节点

public struct FMListNode<T>{
    public var head:FMNode<T>?
    public var size:NSInteger = 0
    public init(){
        
    }
    public var isEmpty:Bool {
        return head == nil
    }
}
extension FMListNode:CustomStringConvertible {
    public var description: String{
        guard let head = head else {
            return "Empty list"
        }
        return String(describing: head)
    }
}

在这里，为了方便以后使用该链表，我们可以添加如下几种方法：

• push: 从头部添加数据
• append: 从尾部添加数据
• get:获取某个节点的数据
• remove：删除某个节点
• reverse:反转链表

其完整代码如下：

public class FMNode<T> {
    public var val:T
    var nextNode:FMNode?
    init(val:T,nextNode:FMNode? = nil) {
        self.val = val
        self.nextNode = nextNode
    }
    
}
extension FMNode:CustomStringConvertible{
    public var description: String{
        guard let nextNode = nextNode else {
            return "\(val)"
        }
        return "\(val) -> " + String(describing: nextNode)
    }
}

public struct FMListNode<T>{
    public var head:FMNode<T>?
    public var size:NSInteger = 0
    public init(){
        
    }
    public var isEmpty:Bool {
        return head == nil
    }
}
extension FMListNode:CustomStringConvertible {
    public var description: String{
        guard let head = head else {
            return "Empty list"
        }
        return String(describing: head)
    }
}
extension FMListNode {
    //从头部增加结点
    mutating func pushNode(val:T){
        let node = FMNode(val: val, nextNode: head)
        node.nextNode = head
        head = node
        size = size + 1
    }
    //从尾部增加结点
    mutating func appendNode(val:T){
        let node = FMNode(val: val,nextNode:nil)
        let tail = self.getNode(at: size - 1)
        if tail == nil {
            head = node
        }else{
            tail!.nextNode = node
        }
        size = size + 1
    }
    //获取某个结点
    func getNode(at:NSInteger) -> FMNode<T>?{
        if isEmpty || head == nil || size == 0 || at < 0 || !(at < size){
            return nil
        }
        var location:NSInteger = 0
        var nextNode = head
        while nextNode != nil {
            if at == location {
                return nextNode
            }
            nextNode = nextNode!.nextNode
            location = location + 1
        }
        return nil
    }
    //删除某个结点
    mutating func removeNode(at:NSInteger) -> Bool{
        if isEmpty || head == nil || size == 0 || at < 0 || !(at < size){
            return false
        }
       
        if at == 0 {
            let mid = head?.nextNode
            head = mid
            size = size - 1
            return true
        }
        var location:NSInteger = 1
        var middleNode:FMNode<T> = head!
        while middleNode.nextNode != nil  {
            if at == location {
                let mid = middleNode.nextNode!.nextNode
                middleNode.nextNode = mid
                size = size - 1
                return true
            }
            middleNode = middleNode.nextNode!
            location = location + 1
        }
        
        return false
    }
}
extension FMListNode{
    //反转单向链表
    mutating func reverseList(){
        if isEmpty {
            return
        }
        var preNode:FMNode<T>? = nil
        var currentNode:FMNode<T> = head!
        print(self)
        //0 -> 2 -> 4 -> 6 -> 8
        while currentNode.nextNode != nil {
            let nextNode:FMNode<T> = currentNode.nextNode!
            currentNode.nextNode = preNode
            preNode = currentNode
            currentNode = nextNode
        }
        currentNode.nextNode = preNode
        head = currentNode
    }
}