swift 实现单链表创建、插入、删除

初始化单链表
创建结点：

        //定义结点
        class Node: NSObject {
              var value: Int = 0
              var next: Node?
          }

      class ListNode: NSObject {
            //头插法
            func initListNodeFromHead(_ array: [Int]) -> Node {
                    var headNode = Node()
                    for data in array {
                          let tempNode = Node()
                          tempNode.value = data
                          tempNode.next = headNode.next
                          headNode.next = tempNode
                     }
                     if headNode.next != nil {
                          headNode = headNode.next!
                      }
                    return headNode
            }

            //尾巴插法
            func initListNodeFromTail(_ array: [Int]) -> Node {
                    var node = Node()
                    var tail = Node()
                    tail = node
                    for data in array {
                          let tempNode = Node()
                          tempNode.value = data
                          tail.next = tempNode
                          tail = tempNode
                    }
                    if node.next != nil {
                       node = node.next!
                    }
                    return node
              }
              //遍历单链表
              public func printList(_ list: inout Node) {
                    var tempList:Node? = list
                    while tempList != nil {
                          print("\(tempList!.value)")
                          if tempList!.next == nil {
                              break
                          }
                          tempList = tempList!.next!
                      }
              }
    }

调用方法执行

      let list1 = ListNode()
      var node = list1.initListNodeFromHead([3,5,12,20])
      list1.printList(&node)

头插入法结果输出：0，20，12，5，3

  var node = list1.initListNodeFromTail([3,5,12,20])

尾插入法结果输出：0，3，5，12，20

为何打印出来的链表前面会多一个0呢？

那是因为初始化链表之前，都初始化了一个头结点，代码：

    var headNode = Node()

所以在方法return之前，需要把头结点的指针指向第一个结点。在方法return的代码之前加上：

      if headNode.next  != nil {
         headNode = headNode.next!
      }

这样输出头插入法输出的结果就是：20，12，5，3

尾插入法输出的结果就是：3，5，12，20

---

下面提供第二种方法

//使用头插入法创建链表
func initListNodeFromHead2(_ array: [Int]) -> Node {
        var headNode:Node?
        for data in array {
            let tempNode = Node()
            tempNode.value = data
            if headNode == nil {
                headNode = tempNode
            } else {
                tempNode.next = headNode
                headNode = tempNode
            }
        }
        return headNode!
    }

//尾巴插法
func initListNodeFromTail2(_ array: [Int]) -> Node {
        var headNode:Node?
        var tail:Node?
        for data in array {
            let tempNode = Node()
            tempNode.value = data
            if tail == nil {
                tail = tempNode
                headNode = tail
            } else {
                tail?.next = tempNode
                tail = tempNode
            }
        }
        return headNode!
    }

输出的结果与第一种一样。

在指定位置中插入结点

func insertData(_ headNode: inout Node, _ pos: Int,_ data: Int) {
        let tempNode = Node()
        tempNode.value = data
        var j = 0
        var tempList = headNode
        while tempList.next != nil && j < pos - 1 {
            tempList = tempList.next!
            j = j + 1
        }
        if j != pos - 1 {
            return
        }
        tempNode.next = tempList.next
        tempList.next = tempNode
    }

调用代码

        let list1 = ListNode()
        var node = list1.initListNodeFromTail2([3,5,12,20])
        list1.insertData(&node,4,30) //在pos为4的下标插入数字30
        list1.printList(&node)

打印结果：3、5、12、20、30

删除指定位置的结点

func deleteData(_ headNode: inout Node, _ pos: Int) -> Int {
        var tempNode:Node?
        var j = 0
        var tempList = headNode
        while tempList.next != nil && j < pos - 1{
            tempList = tempList.next!
            j = j + 1
        }
        if j != pos - 1 {
            return -1
        }
        tempNode = tempList.next
        tempList.next = tempNode?.next
        if tempNode != nil {
            let data = tempNode!.value
            tempNode = nil
            return data
        }
        return -1
    }

调用代码

        let list1 = ListNode()
        var node = list1.initListNodeFromTail2([3,5,12,20])
        list1.insertData(&node,4,30) //在pos为4的下标插入数字30
        list1.printList(&node)
        list1.deleteData(&node, 2)
        list1.printList(&node)

打印结果：3、5、20、30