forked from WenchaoD/LeetCode_Swift
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PartitionList.swift
40 lines (35 loc) · 1.02 KB
/
PartitionList.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Question Link: https://leetcode.com/problems/partition-list/
* Primary idea: Tail Insert and merge two lists, use dummy to avoid edge case
*
* Time Complexity: O(n), Space Complexity: O(1)
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
class PartitionList {
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
let prevDummy = ListNode(0), postDummy = ListNode(0)
var prev = prevDummy, post = postDummy
var node = head
while node != nil {
if node!.val < x {
prev.next = node
prev = prev.next!
} else {
post.next = node
post = post.next!
}
node = node!.next
}
post.next = nil
prev.next = postDummy.next
return prevDummy.next
}
}