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