algoadvance

Leetcode 86. Partition List

Problem Statement:

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Clarifying Questions:

1. What should be done if the list is empty?
   • If the list is empty, the output should also be an empty list.
2. Can the values of the nodes be negative?
   • Yes, the values can be negative.
3. Should we handle the input directly as a linked list, or will it be represented in some other format in the function?
   • The input will be in the form of a ListNode representing the head of the linked list.

Strategy:

1. Create two dummy heads: one for nodes less than x (let’s call it less) and one for nodes greater than or equal to x (greater).
2. Traverse the linked list. For each node, attach it to the end of the less list or the greater list based on its value.
3. After the traversal, link the end of the less list to the beginning of the greater list.
4. Return the head of the less list, skipping over the dummy head.

Code:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        
        // Initialize two dummy heads and their respective tails
        ListNode lessHead = new ListNode(0);
        ListNode greaterHead = new ListNode(0);
        ListNode less = lessHead;
        ListNode greater = greaterHead;
        
        // Traverse the list and partition it
        while (head != null) {
            if (head.val < x) {
                less.next = head;
                less = less.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        
        // Avoid cycle in the linked list by setting the next of greater to null
        greater.next = null;
        // Connect the end of less list to the start of greater list
        less.next = greaterHead.next;
        
        return lessHead.next;
    }
}

Time Complexity:

• The time complexity is O(n), where n is the number of nodes in the linked list. This is because we only traverse the list once.

Space Complexity:

• The space complexity is O(1) since we’re rearranging the nodes in place without using any additional data structure for storing nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?