[Swift]LeetCode86. 分隔链表 | Partition List
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 }