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 step-by-step 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 singly-linked 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.
In-Place: The algorithm can be implemented to run in-place, 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 problem-solving 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.