[Swift]LeetCode147.对链表进行插入排序|InsertionSortList

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
It repeats until no input elements remain.

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

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

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

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

1436ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func insertionSortList(_ head: ListNode?) -> ListNode? {
14         let dummyHead = ListNode(-1)
15         var sortedNodeIdx: ListNode? = dummyHead
16         var curr = head
17         
18         while let _ = curr {
19             while let sortedNodeIdxNext = sortedNodeIdx?.next,
20                 sortedNodeIdxNext.val < curr!.val {
21                     sortedNodeIdx = sortedNodeIdxNext
22             }
23             
24             let currNext = curr?.next
25             let sortedNodeIdxNext = sortedNodeIdx?.next
26             sortedNodeIdx?.next = curr
27             curr?.next = sortedNodeIdxNext
28             sortedNodeIdx = dummyHead
29             curr = currNext
30         }
31         
32         return dummyHead.next
33     }
34 }

2672ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func insertionSortList(_ head: ListNode?) -> ListNode? {
14         let dummyHead = ListNode(0)
15         dummyHead.next = head
16         var last = dummyHead
17         var p = head
18         while p != nil {
19             var tail = p?.next
20             var q = dummyHead
21             while q !== last {
22                 if p!.val < q.next!.val {
23                     p!.next = q.next
24                     q.next = p
25                     last.next = tail
26                     break
27                 }
28                 q = q.next!
29             }
30             if q === last {
31                 last = p!
32             }
33             p = tail
34         }
35         return dummyHead.next
36     }
37 }

2916ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13 
14     func insertionSortList(_ head: ListNode?) -> ListNode? {
15         var result: ListNode? = nil        
16         var cur: ListNode? = head
17         while let curSafe = cur {
18             let newNode = ListNode(curSafe.val)
19             guard let resultSafe = result else {
20                 result = newNode
21                 cur = curSafe.next
22                 continue
23             }
24             if resultSafe.val > curSafe.val {
25                 let resultOld = resultSafe
26                 result = newNode
27                 newNode.next = resultOld
28                 cur = curSafe.next
29                 continue                           
30             }
31             var insertPos: ListNode? = result
32             while insertPos?.next != nil && insertPos!.next!.val < curSafe.val {
33                 insertPos = insertPos?.next
34             }
35             newNode.next = insertPos?.next
36             insertPos?.next = newNode
37             cur = cur?.next
38         }
39         return result
40     }
41 }

3660ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func insertionSortList(_ head: ListNode?) -> ListNode? {
14         if head == nil || head?.next == nil { return head }
15         let dummyNode = ListNode(-1)
16         dummyNode.next = head
17         var sortedIdx: ListNode? = dummyNode
18         var currNode = head?.next
19         head?.next = nil
20 
21         while currNode != nil {
22             while sortedIdx?.next != nil {
23                 if currNode!.val < sortedIdx!.next!.val {
24                     let sortedNext = sortedIdx?.next
25                     let currNext = currNode?.next
26                     sortedIdx?.next = currNode
27                     currNode?.next = sortedNext
28                     currNode = currNext
29                     sortedIdx = dummyNode
30                     break
31                 } else {
32                     sortedIdx = sortedIdx?.next
33                     if sortedIdx?.next == nil {
34                         // currNode is the biggest one in the sortedLinkedList
35                         let currNext = currNode?.next
36                         sortedIdx?.next = currNode
37                         currNode?.next = nil
38                         currNode = currNext
39                         sortedIdx = dummyNode
40                         break
41                     }
42                 }
43             }
44         }
45         
46         return dummyNode.next
47     }
48 }

3994ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     
14     // key = node position
15     // value = node object
16     // var hash: [Int: ListNode] = [:]
17     // var list: ListNode?
18 
19     var array: [ListNode] = []
20     
21     func insertionSortList(_ head: ListNode?) -> ListNode? {
22         guard head != nil,
23             head!.next != nil else {
24             return head
25         }
26         
27         // build array
28         var node = head
29         while node != nil {
30             array.append(node!)
31             node = node!.next
32         }
33         // print("array.count = \(array.count)")
34         
35         // var i = 1 
36         for i in 1..<array.count {
37             // print("i = \(i)")
38             
39             var j = i
40             while j > 0 {
41                 // print("j = \(j)")
42                 if array[j].val < array[j-1].val {
43                     // array[j-1].next = array[j].next
44                     // array[j].next = array[j-1]
45                     array.swapAt(j, j-1)
46                     j -= 1
47                 } else {
48                     break
49                 }
50             }
51         }
52         
53         // connect nodes
54         for i in 0..<array.count-1 {
55             array[i].next = array[i+1]
56         }
57         array[array.count-1].next = nil
58         
59         return array[0]
60     }
61 }