Partition List
To partition the linked list around a value ( x ), you can create two separate linked lists: one for elements less than ( x ), and another for elements greater than or equal to ( x ). After that, you can combine both lists. Here’s a stepbystep guide:
 Create Two Lists: Define two new linked lists,
before
and after
, to hold the nodes less than ( x ) and greater than or equal to ( x ), respectively.  Iterate Through the Original List: Traverse the original linked list and add nodes to either the
before
or after
list, depending on their values relative to ( x ).  Combine the Lists: Connect the end of the
before
list to the beginning of the after
list.  Return the Head: Return the head of the
before
list as the final result.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 class Solution:
def partition(self, head: Optional[ListNode], x: int) > Optional[ListNode]:
before_head = ListNode(0)
before = before_head
after_head = ListNode(0)
after = after_head
current = head
while current:
if current.val < x:
before.next = current
before = before.next
else:
after.next = current
after = after.next
current = current.next
# Make sure the last node of 'after' list points to None
after.next = None
# Connect 'before' list to 'after' list
before.next = after_head.next
return before_head.next

The time complexity is (O(n)), as we are traversing the list once, and the space complexity is (O(1)) since we’re only using a constant amount of extra space.
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
 # Definition for singlylinked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val = 0, _next = nil)
# @val = val
# @next = _next
# end
# end
# @param {ListNode} head
# @param {Integer} x
# @return {ListNode}
def partition(head, x)
list = ListNode.new
first = list
list2 = ListNode.new
second = list2
current = head
while current
if current.val < x
first.next = ListNode.new(current.val)
first = first.next
else
second.next = ListNode.new(current.val)
second = second.next
end
current = current.next
end
first.next = list2.next
return list.next
end

Concept of Patience Sort
Patience Sort is an efficient sorting algorithm that mimics a solitaire card game called “Patience.” In this game, cards are laid out in a sequence of piles according to certain rules. The algorithm works by placing each element from the unsorted array into one of these piles. Finally, the piles are merged together to produce a sorted array. The time complexity of Patience Sort is (O(n \log n)), making it a practical choice for sorting large datasets.
Example Code
Here is an example code snippet in Java, C++, and Python that demonstrates the Patience Sort algorithm.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 import java.util.ArrayList;
import java.util.List;
public class PatienceSort {
public static List<Integer> sort(List<Integer> arr) {
List<List<Integer>> piles = new ArrayList<>();
for (int num : arr) {
// Find the right pile for num
// Custom function findPile() would go here
}
// Merge the piles
// Custom function mergePiles() would go here
return arr;
}
public static void main(String[] args) {
List<Integer> arr = List.of(4, 1, 3, 9, 7);
System.out.println(sort(arr));
}
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 #include <iostream>
#include <vector>
#include <list>
std::vector<int> patienceSort(std::vector<int> arr) {
std::list<std::list<int>> piles;
for (int num : arr) {
// Find the right pile for num
// Custom function findPile() would go here
}
// Merge the piles
// Custom function mergePiles() would go here
return arr;
}
int main() {
std::vector<int> arr = {4, 1, 3, 9, 7};
std::vector<int> sorted = patienceSort(arr);
// Output the sorted array
}

Python
1
2
3
4
5
6
7
8
9
10
11
12
 def patience_sort(arr):
piles = []
for num in arr:
# Find the right pile for num
# Custom function find_pile() would go here
# Merge the piles
# Custom function merge_piles() would go here
return arr
if __name__ == "__main__":
arr = [4, 1, 3, 9, 7]
print(patience_sort(arr))

Key Takeaways
Efficiency: Patience Sort has a time complexity of (O(n \log n)), making it efficient for large datasets.
InPlace: The algorithm can be implemented to run inplace, meaning it doesn’t require additional memory proportional to the input size.
Inspiration: The algorithm draws its inspiration from a solitaire card game, illustrating how everyday activities can inspire efficient problemsolving techniques.
Note: The example code is a skeleton structure. Functions like findPile
and mergePiles
are placeholders for the logic that you’d implement to complete the Patience Sort algorithm.