AADSII-linkedList

前言

程序员还是要懂一点算法和数据结构

算法（algorithm）， 在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列[1]，常用於計算、數據處理和自動推理。精確而言，算法是一個表示爲有限長[2]列表的有效方法。算法應包含清晰定義的指令[3]用於計算函數[4]。(wiki-算法)

数据结构（英语：data structure）是计算机中存储、组织数据的方式。(wiki-数据结构)

链表

//: Playground - noun: a place where people can play

import UIKit

public class singleNode<T:Comparable & Equatable> {
    var value: T
    var next: singleNode<T>?
    var identifier: String
    init(value: T) {
        self.value = value
        self.next = nil
        identifier = UUID().uuidString
    }
    
    public static func != (lhs: singleNode, rhs: singleNode) -> Bool {
        return lhs.identifier != rhs.identifier
    }
    
    public static func == (lhs: singleNode, rhs: singleNode) -> Bool {
        return lhs.identifier == rhs.identifier && lhs.value == rhs.value
    }
    
//    public static func > (lhs: singleNode, rhs: singleNode) -> Bool {
//        return lhs.value > rhs.value
//    }
//
//    public static func < (lhs: singleNode, rhs: singleNode) -> Bool {
//        return lhs.value < rhs.value
//    }
}


extension singleNode: CustomStringConvertible {
    public var description: String {
        return "\(value)"
    }
}

public class singleLinkedList <T:Comparable & Equatable> {
    private var head: singleNode<T>?
    private var tail: singleNode<T>?
    
    public var isEmpty: Bool {
        return head == nil
    }
    
    public var first: singleNode<T>? {
        return head
    }
    
    public var last: singleNode<T>? {
        return tail
    }
    
    public func append(value: T) {
        let newNode = singleNode(value: value);
        
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
    
    public func makeCycleAt(index: Int) ->Bool {
        if let cycleNode = self.nodeAt(index: index) {
            tail?.next = cycleNode
            return true
        }
        return false
    }
    
    public func makeTailNextTo(node: singleNode<T>?) -> Bool {
        if node == nil { return false }
        tail?.next = node
        return true
    }
    
    class public func getLinkLength(nodeH: singleNode<T>?) ->Int {
        var node = nodeH
        var length = 0
        while node != nil {
            length = length + 1
            node = node?.next
        }
        return length
    }
    // 1. 遍历
    public func enumerateElements() {
        var node = head
        while node != nil {
            node = node?.next
        }
    }
    // 2. 反转
    public func reverse() {
        if head == nil || head?.next == nil {
            return
        }
        
        var pre:singleNode<T>?
        var cur: singleNode<T>? = head
       
        while cur != nil {
            let tmp = cur?.next //keep the next node
            cur?.next = pre //cut cur.next to null
            pre = cur   //put cur to pre
            cur = tmp  //put next to cur
        }
        tail = head
        head = pre
    }
    //3. 查找
    public func nodeAt(index: Int) -> singleNode<T>? {
        if head == nil { return nil }
        var node = head
        var i = index
        while node != nil {
            if i == 0 {
                break
            }
            node = node!.next
            i = i - 1
        }
        return node
    }
    //4. 中间节点
    public func findMidNode()->singleNode<T>? {
        var fNode = head
        var midNode = head
        while (fNode != nil && fNode?.next != nil) {
            fNode = fNode?.next?.next
            midNode = midNode?.next
        }
        return midNode
    }
    //5. 两个有序单链表合并
    class func mergeSortedLinkedList(lhead:singleNode<T>?, rhead:singleNode<T>?) ->singleNode<T>? {
        if lhead == nil { return rhead }
        if rhead == nil { return lhead }
        var newHead: singleNode<T>? = nil
        if lhead!.value < rhead!.value {
            newHead = lhead
            newHead?.next = mergeSortedLinkedList(lhead: lhead?.next, rhead: rhead)
        } else {
            newHead = rhead
            newHead?.next = mergeSortedLinkedList(lhead: lhead, rhead: rhead?.next)
        }
        return newHead
    }
    //6. 是否有环
    public func hasCycle() ->Bool {
        var runNode = head
        var walkNode = head

        while runNode != nil && runNode?.next != nil {
            runNode = runNode?.next?.next
            walkNode = walkNode?.next
            if let run = runNode, let walk = walkNode, run == walk {
                return true
            }
        }
        return false
    }
    //7. 环内相遇的节点
    class public func getCycleNode(cycleNode: singleNode<T>?) ->singleNode<T>? {
        var runNode = cycleNode
        var walkNode = cycleNode
        
        while runNode != nil && runNode?.next != nil {
            runNode = runNode?.next?.next
            walkNode = walkNode?.next
            if let run = runNode, let walk = walkNode, run == walk {
                return walk
            }
        }
        return nil
    }
    //8. 环的入口点
    public func detectCycle() ->singleNode<T>? {
        var runNode = head
        var walkNode = head
        while runNode != nil && runNode?.next != nil {
            runNode = runNode?.next?.next
            walkNode = walkNode?.next
            if let run = runNode, let walk = walkNode, run == walk {
                break
            }
        }
        if runNode == nil || runNode?.next == nil {
            return nil
        }
        
        var headWalkNode = head
        var crossWalkNode = walkNode
        while let headWalk = headWalkNode, let crossWalk = crossWalkNode, headWalk != crossWalk {
            headWalkNode = headWalkNode?.next
            crossWalkNode = crossWalkNode?.next
        }
        return headWalkNode
    }
    //9. 是否相交
    class public func isIntersect( lhead: singleNode<T>?, rhead: singleNode<T>?) ->Bool {
        if lhead == nil || rhead == nil { return false }
        var left = lhead
        var right = rhead
        while left?.next != nil {
            left = left?.next
        }
        
        while right?.next != nil {
            right = right?.next
        }
        if let l = left, let r = right, l == r {
            return true
        }
        return false
    }
    //10. 有环链表是否相交
    class public func isIntersectWithLoop(lhead: singleNode<T>?, rhead: singleNode<T>?) ->Bool {
        guard let l = singleLinkedList.getCycleNode(cycleNode: lhead) else { return false }
        guard let r = singleLinkedList.getCycleNode(cycleNode: rhead) else { return false }

        var temp = l.next
        while temp! != l {
            if temp! == r {
                return true
            }
            temp = temp?.next
        }
        
        return false
    }
    //11. 相交的第一个公共节点
    class public func findIntersectNod(lhead: singleNode<T>?, rhead: singleNode<T>?) ->singleNode<T>? {
        let lenl = singleLinkedList.getLinkLength(nodeH: lhead)
        let lenr = singleLinkedList.getLinkLength(nodeH: rhead)
        
        var l = lhead
        var r = rhead
        
        if lenl > lenr {
            for _ in 0..<(lenl - lenr) {
                l = l?.next
            }
        } else {
            for _ in 0..<(lenr - lenl) {
                r = r?.next
            }
        }
        
        while l != nil {
            if let ll = l, let rr = r, ll == rr {
                return l
            }
            l = l?.next
            r = r?.next
        }
        
        return nil
    }
    //12. O(1) 时间内删除链表节点
    public func remove(nodeToDel: singleNode<T>) {
        if head == nil { return }
        var tempNode: singleNode<T>?
        
        if nodeToDel == head! {//node to delete is head
            head = head?.next
            nodeToDel.next = nil
            return
        }
        
        if nodeToDel.next == nil {//node to delete is tail
            tempNode = head
            while (tempNode?.next)! != nodeToDel {
                tempNode = tempNode?.next
            }
            tempNode?.next = nil
            tail = tempNode
            return
        }
        //node to delete is middle
        nodeToDel.value = (nodeToDel.next?.value)!
        tempNode = nodeToDel.next?.next
        nodeToDel.next?.next = nil
        nodeToDel.next = tempNode
    }
    //链表倒数第K个节点
    public func theLastKthNode(index: Int) ->singleNode<T>? {
        if index < 0 { return nil }
        var slowNode = head
        var fastNode = head
        var i = index
        
        while i > 0 && fastNode != nil {
            i = i - 1
            fastNode = fastNode?.next
        }
        
        if i > 0 { return nil }
        
        while fastNode != nil {
            slowNode = slowNode?.next
            fastNode = fastNode?.next
        }
        return slowNode
    }
}

extension singleLinkedList: CustomStringConvertible {
    public var description: String {
        var text = "["
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil { text += "," }
        }
        return text + "]"
    }
}

var linkInt1 = singleLinkedList<Int>()
linkInt1.append(value: 8)
linkInt1.append(value: 7)
linkInt1.append(value: 6)
linkInt1.append(value: 5)
linkInt1.append(value: 4)
linkInt1.append(value: 3)
linkInt1.append(value: 2)
linkInt1.append(value: 1)

var linkInt2 = singleLinkedList<Int>()
linkInt2.append(value: 1)
linkInt2.append(value: 2)
linkInt2.append(value: 3)
linkInt2.append(value: 4)
linkInt2.append(value: 9)
linkInt2.append(value: 10)
linkInt2.append(value: 11)
linkInt2.append(value: 12)

var cycleLink = singleLinkedList<Int>()
cycleLink.append(value: 1)
cycleLink.append(value: 2)
cycleLink.append(value: 3)
cycleLink.append(value: 4)
cycleLink.append(value: 5)
cycleLink.append(value: 6)
cycleLink.append(value: 7)
cycleLink.append(value: 8)
cycleLink.makeCycleAt(index: 5)

var intersect = singleLinkedList<Int>()
intersect.append(value: 1)
intersect.append(value: 2)
intersect.append(value: 3)
intersect.append(value: 4)
intersect.append(value: 9)
intersect.append(value: 10)
intersect.append(value: 11)
intersect.append(value: 12)

var intersect1 = singleLinkedList<Int>()
intersect1.append(value: 1)
intersect1.append(value: 2)
intersect1.append(value: 3)
intersect1.append(value: 4)
intersect1.append(value: 9)
intersect1.append(value: 10)
intersect1.append(value: 11)
intersect1.append(value: 12)

print("↓↓↓单链表遍历↓↓↓")
linkInt1.enumerateElements()
print("↑↑↑单链表遍历↑↑↑")

print("↓↓↓单链表反转↓↓↓")
linkInt1.reverse()
print("↑↑↑单链表反转↑↑↑")

print("↓↓↓倒序打印↓↓↓")
linkInt1.reverse()
var temp = linkInt1.first
while temp != nil {
    print(temp as Any)
    temp = temp?.next
}
print("↑↑↑倒序打印↑↑↑")

print("↓↓↓删除链表节点↓↓↓")
var deleteNode = linkInt1.nodeAt(index: 5)
linkInt1.remove(nodeToDel: linkInt1.nodeAt(index: 5)!)
print("↑↑↑删除链表节点↑↑↑")

print("↓↓↓中间节点↓↓↓")
linkInt1.findMidNode()
print("↑↑↑中间节点↑↑↑")

print("↓↓↓有序单链表合并↓↓↓")
var newLinkHead = singleLinkedList.mergeSortedLinkedList(lhead: linkInt1.first, rhead: linkInt2.first)
print("↑↑↑有序单链表合并↑↑↑")

print("↓↓↓链表是否有环↓↓↓")
linkInt1.hasCycle()
cycleLink.hasCycle()
print("↑↑↑链表是否有环↑↑↑")

print("↓↓↓链表环入口↓↓↓")
cycleLink.detectCycle()
print("↑↑↑链表环入口↑↑↑")

print("↓↓↓链表是否相交↓↓↓")
singleLinkedList.isIntersect(lhead: linkInt1.first, rhead: linkInt2.first)
var intersectNode = intersect.nodeAt(index: 5)
linkInt1.makeTailNextTo(node: intersectNode)
singleLinkedList.isIntersect(lhead: linkInt1.first, rhead: intersect.first)
print("↑↑↑链表是否相交↑↑↑")

print("↓↓↓链表相交的第一个节点↓↓↓")
singleLinkedList.findIntersectNod(lhead: linkInt1.first, rhead: intersect.first)
print("↑↑↑链表相交的第一个节点↑↑↑")

print("↓↓↓有环链表是否相交↓↓↓")
intersect1.makeTailNextTo(node: cycleLink.nodeAt(index: 3))
singleLinkedList.isIntersectWithLoop(lhead: cycleLink.first, rhead: intersect1.first)
print("↓↓↓有环链表是否相交↓↓↓")



public class Node <Element> {
    var value: Element
    var next: Node<Element>?
    var previous: Node<Element>?

    init(value: Element) {
        self.value = value
    }
}

extension Node: CustomStringConvertible {
    public var description: String {
        return "\(value)"
    }
}

public class linkedList <Element> {
    fileprivate var head: Node<Element>?
    private var tail: Node<Element>?

    public var isEmpty: Bool {
        return head == nil
    }

    public var first: Node<Element>? {
        return head
    }

    public var last: Node<Element>? {
        return tail
    }

    public func append(value: Element) {
        let newNode = Node(value: value)

        if let tailNode = tail {
            tailNode.next = newNode
            newNode.previous = tailNode
        } else {
            head = newNode
        }
        tail = newNode
    }

    public func remove(node: Node<Element>) ->Element {
        let prev = node.previous
        let next = node.next

        if let prev = prev {
            prev.next = next
        } else {
            head = next
        }

        next?.previous = prev

        if next == nil {
            tail = prev
        }

        node.previous = nil
        node.next = nil

        return node.value
    }

    public func removeAll() {
        head = nil
        tail = nil
    }

    public func nodeAt(index: Int) -> Node<Element>? {
        if index >= 0 {
            var node = head
            var i = index
            while node != nil {
                if i == 0 {return node}
                i -= 1
                node = node!.next
            }
        }
        return nil
    }

    //遍历
    public func enumerateElements() {
        print("↓↓↓双链表遍历↓↓↓")
        var node = head
        while node != nil {
            print("\(node!.value)")
            node = node?.next
        }
        print("↑↑↑双链表遍历↑↑↑")
    }

    //反转
//    public func reverse() {
//        var node = head
//        var temp: Node<Element>
//        while node != nil {
//
//        }
//
//    }
}

extension linkedList: CustomStringConvertible {
    public var description: String {
        var text = "["
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil { text += "," }
        }
        return text + "]"
    }
}

let dogBreeds = linkedList<String>()
dogBreeds.append(value: "dog1")
dogBreeds.append(value: "dog2")
dogBreeds.append(value: "dog4")
dogBreeds.append(value: "dog3")
dogBreeds.enumerateElements()
print(dogBreeds)
dogBreeds.remove(node: dogBreeds.nodeAt(index: 2)!)
print(dogBreeds)

//队列 FIFO
public struct Queue <Element> {
    fileprivate var list = linkedList<Element>()
    public var isEmpty: Bool {return list.isEmpty}
    
    public mutating func enqueue(_ element: Element) {
        list.append(value: element)
    }
    
    public mutating func dequeue() ->Element? {
        guard !isEmpty, let element = list.first else {
            return nil
        }
        list.remove(node: element)
        return element.value
    }
    
    public func peek() ->Element? { return list.first?.value }
}

extension Queue: CustomStringConvertible {
    public var description: String {
        return list.description
    }
}

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(5)
queue.enqueue(4)
print(queue)
queue.dequeue()
print(queue)