Which one is the better solution


  • 0
    H

    The following is my accepted solution:

    public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        
        ListNode leftEnd = null; //the end of the first half (nodes which have the smaller value than x)
        ListNode previous = null;
        
        if (head.val < x) {
            leftEnd = head;
        } 
        previous = head;
        
        ListNode node = head.next; 
        
        while (node != null) {
            if (node.val < x) { 
                if (leftEnd == null || leftEnd.next != node) { //need to insert into the first half
                    previous.next = node.next;
                    if(leftEnd != null) { //insert the node
                        node.next = leftEnd.next;
                        leftEnd.next = node;
                    } else if (leftEnd == null){ //the first one which is less than x, let it be the new head
                        node.next = head;
                        head = node;
                    }
                    leftEnd = node;
                    node = previous.next;
                    continue;
                } else { //not need to insert, just move the leftEnd
                    leftEnd = node;
                }
                
            }
            //node.val > x
            previous = node;
            node = node.next;
        }
        
        return head;
    }
    }
    

    And I know there is another way to solve this question. We can construct two sub lists, one is for the nodes with smaller value and another is for larger value. And then concatenate such two lists to get the final list.

    So which one is better? Do we need any extra space to use two sub lists?


  • 2
    V

    In the algorithm where two sub lists are used to construct the resultant linked list, space complexity is O(1) as for the two separate lists only pointers are used no space is created for them.

    class Solution{
     public:
    ListNode *partition(ListNode *head, int x)
     {
            ListNode *left = NULL, *right = NULL, **p = &left, **q = &right, *entry = head;
    
            while (entry) {
                if (entry->val < x) {
                    *p = entry; p = &(entry->next); entry = *p;
                    }
                    else {
                    *q = entry; q = &(entry->next); entry = *q;
                }
            }
            *p = right; *q = NULL;
            return left;
     }
     };

  • 0
    T

    your solution is exactly the same as mine. I have seen many link list problems. It's sad that most people didn't understand pointers. Nice Code!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.