题目

对链表进行插入排序

问题:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。

说明:

不允许修改给定的链表

示例:

示例 1：
     
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路:

从链表头部开始遍历，记录当前要插入排序的节点和其上一个节点，对每个节点执行如下操作：从头部开始找到当前节点之前第一个不大于它的节点，记录找到的节点以及它前一个节点如果它前一个节点为空，说明要插入到头节点之前，若不为空，则插入到该节点之后继续进行下一次插入排序，直到遍历到链表尾部。

代码：

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}

extension SingNode : CustomStringConvertible {
    public var description: String {
        var string = "\(value)"
        var node = self.nextNode
        
        while node != nil {
            string = string + " -- " + "\(node!.value)"
            node = node?.nextNode
        }
        return string
    }
}
 **/
      
func insertionSortList(_ l1:SingNode?) -> SingNode? {
        if l1 == nil || l1?.nextNode == nil {
            return l1
        }
        
        let dummyNode = SingNode.init(value: Int(INT16_MIN))
        var pre = dummyNode
        var cur = l1
        var rear:SingNode? = nil
        
        while cur != nil {
            rear = cur?.nextNode
            while pre.nextNode != nil && pre.nextNode!.value < cur!.value {
                pre = pre.nextNode!
            }
            cur?.nextNode = pre.nextNode
            pre.nextNode = cur
            cur = rear
            pre = dummyNode
        }
        return dummyNode.nextNode
    }