My Java Solution without using extra "Nodes" or space


  • 1

    I see most of the solutions are creating two extra ListNode objects. My solution only uses two ListNode pointers to change the input LinkedList.

    Though the solution is long, no extra ListNode objects is needed.

    public class Solution {
      public ListNode partition(ListNode head, int x) {
        ListNode s=null,l=null,cur=head,ll=null, ss=null;
        //find start of s
        while((s==null || l==null) && cur!=null){
          if(cur.val<x && s==null) s = cur;
          else if(cur.val>=x && l==null) l=cur;
          cur = cur.next;
        }
        //ss is the head of first half, ll is the head of second half
        ss = s;
        ll=l;
        //if all elements are less or bigger than x
        if(s==null || l==null || l.next==null) return head;
        cur = head;
        while(cur!=null){
          if(cur==s || cur==l){
            cur = cur.next;
            continue;
          }
          if(cur.val<x && cur!=s){
            s.next = cur;
            s = s.next;
          }
          else if (cur.val>=x && cur!=l){
            l.next = cur;
            l = l.next;
          }
          cur = cur.next;
        }
        //concatenate
        s.next = ll;
        //set the tail of second half
        l.next = null;
        return ss;
      }
    }

Log in to reply
 

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