Using one pass with One dummyNode


  • 0
    M

    Main idea is using two pointer, cur and fast;
    cur is node to add the node which is less x;
    fast is node to go through all the nodes, to determine if fast.next.val is smaller than x or not;
    ''''
    public class Solution {
    public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null) return head;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    ListNode fast = dummy;
    while (fast.next != null) {
    if (fast.next.val >= x) fast = fast.next;
    else{
    if (cur == fast) {
    fast = fast.next;
    cur = fast;
    }
    else {
    ListNode temp = fast.next.next;
    ListNode temp2 = cur.next;
    cur.next = fast.next;
    fast.next = temp;
    cur = cur.next;
    cur.next = temp2;
    }
    }
    }
    return dummy.next;
    }
    }
    ''''


Log in to reply
 

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