美文网首页程序员Swift - LeetCodeSwift in LeetCode
Swift - LeetCode - 对链表进行插入排序

Swift - LeetCode - 对链表进行插入排序

作者: 依赖糊涂 | 来源:发表于2019-03-09 23:16 被阅读3次

    题目

    对链表进行插入排序

    问题:

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

    说明:

    不允许修改给定的链表

    示例:

    示例 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
        }
    
    

    相关文章

      网友评论

        本文标题:Swift - LeetCode - 对链表进行插入排序

        本文链接:https://www.haomeiwen.com/subject/fvrypqtx.html