How would you partition a linked list around a value x?

Partitioning a linked list around a value x is a common task. The aim is to rearrange the elements in the list so that all nodes less than x come before all nodes greater than or equal to x.

We can achieve this using following approach:

- Initialize two separate linked lists named ‘listSecondsHalf‘ and ‘listFirstHalf‘, one to store nodes greater than or equal to the value x and the other to store nodes smaller than x.

- Iterate over the original list and add nodes to ‘listFirstHalf‘ and ‘listSecondsHalf‘ list as per their data value.

- Finally, merge ‘listFirstHalf‘ and ‘listSecondsHalf‘.

Here is the pseudocode for better understanding:

function partitionList(head, x):
    listFirstHalf = new LinkedList()  # a new linked list
    listSecondHalf = new LinkedList()  # another linked list

    node = head  # start from the head of the given linked list

    while node != null:  # iterate through the original list
        if node.data < x:
            listFirstHalf.add(node.data)  # add to the first linked list if smaller
        else:
            listSecondHalf.add(node.data)  # add to the second linked list if larger

        node = node.next  # move to the next node

    if listFirstHalf.head == null:  # if first list is empty, then return the second list
        return listSecondHalf
    elif listSecondHalf.head == null:  # if second list is empty, then return the first list
        return listFirstHalf

    listFirstHalfTail = getTail(listFirstHalf)  # get tail of first list
    listFirstHalfTail.next = listSecondHalf.head  # connect the first list's tail with the second list's head

    return listFirstHalf  # return the partitioned list

This pseudocode is not language-specific, but it gives an idea about how to approach the problem. In a real coding interview, I would turn this into the language required by the interviewer.

The time complexity of this approach is O(n), where n is the number of nodes in the linked list because you have to traverse the list once to sort the nodes. The space complexity is also O(n) as we are storing the nodes into new linked lists.

It’s important to note we maintain the relative ordering of nodes in this approach i.e. nodes with same values keep their original ordering. This hence is a stable algorithm.