subject

Insert and sort the linked list

Question:

Insertion sorting is iterative, moving only one element at a time until all elements form an ordered output list. In each iteration, insert sorting only removes one element to be sorted from the input data, finds its proper position in the sequence, and inserts it. Repeat until all input data has been inserted.

Explain:

Modifying the given linked list is not allowed

Example:

Example 1:
     
Input: 4 - > 2 - > 1 - > 3
 Output: 1 - > 2 - > 3 - > 4

Example 2:
Input: - 1 - > 5 - > 3 - > 4 - > 0
 Output: - 1 - > 0 - > 3 - > 4 - > 5

Solutions:

Start traversing from the head of the chain list, record the nodes to be inserted and sorted and the previous node. For each node, perform the following operations: find the first node no larger than the current node from the head, record the found node and the previous node. If the previous node is empty, it means to insert the node before the head node. If it is not empty, insert the node After that, the next insertion sort will be continued until the end of the list is traversed.

Code:

/**
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
    }