[Swift]LeetCode86.分隔链表|PartitionList

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

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

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

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

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

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

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

16ms

 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 partition(_ head: ListNode?, _ x: Int) -> ListNode? {
14         var head = head
15         
16         var leftHead = ListNode(0)
17         let leftDummy = leftHead
18         
19         var rightHead = ListNode(0)
20         var rightDummy = rightHead
21         
22         while head != nil {
23             if head!.val < x {
24                 leftHead.next = head
25                 leftHead = leftHead.next ?? ListNode(0)
26             }else {
27                 rightHead.next = head
28                 rightHead = rightHead.next ?? ListNode(0)
29             }
30             head = head!.next
31         }
32         
33         leftHead.next = rightDummy.next
34         rightHead.next = nil
35         return leftDummy.next
36     }
37 }

16ms

 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 partition(_ head: ListNode?, _ x: Int) -> ListNode? {
14         let prevDummy = ListNode(0), postDummy = ListNode(0)
15         var prev = prevDummy, post = postDummy
16         
17         var node = head
18         
19         while node != nil {
20             let next = node!.next
21             node!.next = nil
22 
23             if node!.val < x {
24                 prev.next = node
25                 prev = prev.next!
26             } else {
27                 post.next = node
28                 post = post.next!
29             }
30             node = next
31         }
32         
33         prev.next = postDummy.next
34         
35         return prevDummy.next
36     }
37 }

20ms

 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 partition(_ head: ListNode?, _ x: Int) -> ListNode? {
14         let dummyHead1 = ListNode(0)
15         let dummyHead2 = ListNode(0)
16         var p1 = dummyHead1
17         var p2 = dummyHead2
18         var p = head
19         while p != nil {
20             if p!.val < x {
21                 p1.next = p
22                 p1 = p!
23             } else {
24                 p2.next = p
25                 p2 = p!
26             }
27             p = p!.next
28         }
29         p1.next = dummyHead2.next
30         p2.next = nil
31         return dummyHead1.next
32     }
33 }