Beats 100% Solution


  • 0
    W

    /**

    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      class Solution {
      public ListNode partition(ListNode head, int x) {
      if (head == null) return null;
      ListNode bigNode = head,bigPre = null,ret = null;//bigNode is the first node whose value not less than x.bigPre is bigNode's previous node,which might be null when the first node of the linkedList bigger than x.
      while (bigNode != null && bigNode.val < x){//find the bigNode
      bigPre = bigNode;
      bigNode = bigNode.next;
      }
      ListNode p = bigNode,q = bigPre;
      while (p != null){
      if (p.val < x){//p needs to be inserted
      q.next = p.next;
      if (bigPre != null)
      bigPre.next = p;
      else ret = p;//When bigPre is null,if there is a node less than x,we should return this node.
      p.next = bigNode;
      bigPre = p;
      }
      else q = p;
      p = q.next;
      }
      return ret == null? head:ret;
      }
      }

Log in to reply
 

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