题目
对链表进行插入排序
问题:
插入排序是迭代的, 每次只移动一个元素, 直到所有元素可以形成一个有序的输出列表. 每次迭代中, 插入排序只从输入数据中移除一个待排序的元素, 找到它在序列中适当的位置, 并将其插入. 重复直到所有输入数据插入完为止.
说明:
不允许修改给定的链表
示例:
示例 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
- }
来源: http://www.jianshu.com/p/aaa4bc449121