/**
 * 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 {
            let next = node!.next
            node!.next = nil

            if node!.val < x {
                prev.next = node
                prev = prev.next!
            } else {
                post.next = node
                post = post.next!
            }
            node = next
        }
        
        prev.next = postDummy.next
        
        return prevDummy.next
    }
}
/**
 * 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
    }
}
--- 
+++ 
@@ -22,6 +22,9 @@
         var node = head
         
         while node != nil {
+            let next = node!.next
+            node!.next = nil
+
             if node!.val < x {
                 prev.next = node
                 prev = prev.next!
@@ -29,10 +32,9 @@
                 post.next = node
                 post = post.next!
             }
-            node = node!.next
+            node = next
         }
         
-        post.next = nil
         prev.next = postDummy.next
         
         return prevDummy.next
[LinkedList] Optimize solution to Partition List
