链表算法

class Node<T> {
    var value: T
    var next: Node<T>?
    init(_ val: T) {
        self.value = val
        self.next = nil
    }
}

class IntLinkList {
    var head: Node<Int>?
    var tail: Node<Int>?
    
    init() {
        tail = nil
        head = tail
    }
    
    var isEmpty: Bool {
        get {
            return head == nil
        }
    }
    
    func append(value: Int) {
        let node = Node(value)
        if tail == nil {
            tail = node
            head = tail
        } else {
            tail!.next = node
            tail = tail!.next
        }
    }
    
    func appendToHead(value: Int) {
        let node = Node(value)
        if head == nil {
            head = node
            tail = head
        } else {
            node.next = head?.next
            head = node
        }
    }
    
    func insertAt(index: Int, value: Int) {
        if index == 0 {
            self.appendToHead(value: value)
        }
        
        var tmp = head
        
        var i: Int = 0
        
        while i != index && tmp == nil {
            tmp = tmp?.next
            i+=1
        }
        
        if i == index {
            let node = Node(value)
            node.next = tmp?.next
            tmp?.next = node
        } else {
            //说明index太大，还没到，链表就走完了
            self.append(value: value)
        }
    }
}

//left和right是已经排好序的链表
    func bindTwoLink(firstList left: IntLinkList, second right: IntLinkList) -> IntLinkList {
        guard !left.isEmpty else {return right}
        
        guard !left.isEmpty else {return right}
        
        let list = IntLinkList()
        
        var currentLeft = left.head
        var currentRight = right.head
        
        if let leftNode = currentLeft , let rightNode = currentRight {
            if leftNode.value < rightNode.value {
                list.head = leftNode
                currentLeft = leftNode.next
            } else {
                list.head = rightNode
                currentRight = rightNode.next
            }
            list.tail = list.head
        }
        
        while let leftNode = currentLeft, let rightNode = currentRight {
            if leftNode.value < rightNode.value {
                list.tail?.next = leftNode
                currentLeft = leftNode.next
            } else {
                list.tail?.next = rightNode
                currentRight = rightNode.next
            }
            list.tail = list.tail?.next
        }
        
        //此处还有最后两个尾端没有遍历到
        if let leftNode = currentLeft {list.tail?.next = leftNode}
        if let rightNode = currentRight {list.tail?.next = rightNode}
        
        return list
    }

let list1 = IntLinkList()
list1.append(value: 1)
list1.append(value: 2)
list1.append(value: 4)
list1.append(value: 5)
list1.append(value: 22)

let list2 = IntLinkList()
list2.append(value: 1)
list2.append(value: 3)
list2.append(value: 4)
list2.append(value: 5)
list2.append(value: 6)
list2.append(value: 7)
list2.append(value: 8)

let list = solution.bindTwoLink(firstList: list1, second: list2)

var head = list.head

while head?.next != nil  {
    print(head!.value as Any, terminator: " ")
    head = head!.next
}

print(head!.value)

func reverseList(_ head: Node<Int>?) -> Node<Int>? {
  var cur = head
  var last: Node<Int>?
  var next: Node<Int>?

  while (cur != nil) {
    next = cur?.next
    cur?.next = last
    last = cur
    cur = next
  }

  return last
}