Can anyone provide a solution without using the dummy node?


  • 0
    B

    This solution is not appropriate if the information in each node is huge. Is there any way of doing this without the dummy node?


  • 0
    K
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode Partition(ListNode head, int x) {
            ListNode left = null;
            ListNode rightHead = null;
            ListNode rightTail = null;
            ListNode result = head;
            
            while (head != null)
            {
                if (head.val < x)
                {
                    if (left == null)
                    {   
                        ListNode next = head.next;
                        left = head;
                        left.next = null;
                        result = left;
                        head = next;
                    }
                    else
                    {
                        ListNode next = head.next;
                        left.next = head;
                        left = left.next;
                        left.next = null;
                        head = next;
                    }
                }
                else
                {
                    if (rightHead == null)
                    {
                        ListNode next = head.next;
                        rightHead = head;
                        rightTail = head;
                        rightHead.next = null;
                        rightTail.next = null;
                        head = next;
                    } else
                    {
                        ListNode next = head.next;
                        rightTail.next = head;
                        rightTail = rightTail.next;
                        rightTail.next = null;
                        head = next;
                    }
                }
            }
            if (left == null) return rightHead;
            left.next = rightHead;
            return result;
        }
    }

  • 1
    ListNode* partition(ListNode* head, int x) {
        if(head==NULL) return NULL;
        ListNode * pBig=NULL,*pBigHead=NULL,*pSmall=NULL,*pSmallHead=NULL;
        
        while(head!=NULL){
            if(head->val<x){
                if(pSmall==NULL){
                    pSmall=head;
                    pSmallHead=head;
                }
                else{
                    pSmall->next=head;
                    pSmall=head;
                }
            }
            else{
                if(pBig==NULL){
                    pBig=head;
                    pBigHead=head;
                }
                else{
                    pBig->next=head;
                    pBig=head;
                }
            }
            head=head->next;
        }
        if(pBigHead!=NULL) pBig->next=NULL;
        
        if(pSmallHead!=NULL) pSmall->next=pBigHead;
        else pSmallHead=pBigHead;
        
        return pSmallHead;
    }

  • 0
    E

    class Solution
    {
    public:

    ListNode * partition(ListNode * head, int x)
    {
        if (head == NULL)
        {
            return NULL;
        }
        
        ListNode * pstHead = head;
        ListNode * pstTail = head;
        
        while (pstTail -> next != NULL)
        {
            pstTail = pstTail -> next;
        }
        
        if (pstHead == pstTail)
        {
            return pstHead;
        }
        
        ListNode * pstWorkerCurr = pstHead;
        ListNode * pstWorkerTail = pstTail;
        
        while (pstWorkerCurr != pstWorkerTail)
        {
            if (pstWorkerCurr -> val < x)
            {
                pstWorkerCurr = pstWorkerCurr -> next;
            }
            else
            {
                ListNode * pstDelete = pstWorkerCurr -> next;
                swap(pstWorkerCurr, pstDelete);
                
                if (pstDelete != pstTail)
                {
                    pstWorkerCurr -> next = pstDelete -> next;
                    pstDelete     -> next = NULL;
                    pstTail       -> next = pstDelete;
                    pstTail               = pstDelete;
                }
                
                if (pstDelete == pstWorkerTail)
                {
                    break;
                }
            }
        }
        
        if (pstWorkerCurr -> val >= x)
        {
            ListNode * pstDelete = pstWorkerCurr -> next;
            
            if (pstDelete != NULL)
            {
                swap(pstWorkerCurr, pstDelete);
                
                if (pstDelete != pstTail)
                {
                    pstWorkerCurr -> next = pstDelete -> next;
                    pstDelete     -> next = NULL;
                    pstTail       -> next = pstDelete;
                    pstTail               = pstDelete;
                }
            }
        }
        
        return pstHead;
    }
    

    private:

    void swap(ListNode * pstNode1, ListNode * pstNode2)
    {
        int iSwapValue  = pstNode1 -> val;
        pstNode1 -> val = pstNode2 -> val;
        pstNode2 -> val = iSwapValue;
    }
    

    };


Log in to reply
 

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