链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

单向链表

单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针，下面Demo为单向列表的定义

双向链表

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

链表操作

1.从后面删除第N个节点

func removeNthFromEnd(node:ListNode,n:Int) -> ListNode {
    if node.next == nil || n <= 0 {
        return node
    }
    let tempNode = ListNode(x:0)
    tempNode.next = node
    var p = tempNode,q = tempNode
    for _ in 0..<n {
        if p.next == nil {
            return tempNode
        }else{
            p = p.next ?? ListNode()
        }
    }
    p.showNode()
    while (p.next != nil) {
        p = p.next ?? ListNode()
        q = q.next ?? ListNode()
    }
    q.next = q.next?.next
    return tempNode.next ?? ListNode()
}

2.从正面删除节点

func removeNthFromNode(node:ListNode,n:Int) -> ListNode {
    if node.next == nil || n <= 0 {
        return node
    }
    var tempNode = node
    var nodeArr:[ListNode] = [node]
    while tempNode.next != nil {
        nodeArr.append(tempNode.next ?? ListNode())
        tempNode = tempNode.next ?? ListNode()
    }
    if nodeArr.count < n {
        return node
    }
    if n == 1 {
        //删除头
        return nodeArr[1]
    }
    if n == nodeArr.count {
        //删除尾
        let n:ListNode = nodeArr[n-1]
        n.next = nil
        return nodeArr[0]
    }
    let nodeNBefor = nodeArr[n-2]
    let nodeNAfter = nodeArr[n]
    nodeNBefor.next = nodeNAfter
    return nodeArr[0]
}

3.单向链表定义Node

class ListNode: NSObject {
    var val:Int = 0
    var next:ListNode?
   convenience init(x:Int) {
        self.init()
        self.val = x
    }
    func loadNode(arr:[Int]){
        if arr.count == 0 {
            return
        }
        self.val = arr[0]
        var cur = self
        for i in 1..<arr.count{
            cur.next = ListNode(x: arr[i])
            cur = cur.next ?? ListNode()
        }
    }
    func showNode() {
        var cur = self
        var res:String = ""
        while cur.next != nil {
            res.append(String.init(cur.val)+"->")
            cur = cur.next ?? ListNode()
            if cur.next == nil {
                res.append(String.init(cur.val)+"->")
            }
        }
        print(res)
    }
}