Java One Pass Solution with Constant Space


  • 0
    M
    public class Solution {
      public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = new ListNode(0);
        ListNode firstPtr = first;
        ListNode second = new ListNode(0);
        ListNode secondPtr = second;
        ListNode ptr = head;
        while (ptr != null) {
           if (ptr.val < x) {
               firstPtr.next = ptr;
               firstPtr = firstPtr.next;
               ptr = ptr.next;
               firstPtr.next = null;
           } else {
               secondPtr.next = ptr;
               secondPtr = secondPtr.next;
               ptr = ptr.next;
               secondPtr.next = null;
           }
        }
        firstPtr.next = second.next;
    
        return first.next;
    
      }
    }
    

Log in to reply
 

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