Same Question But Use Array To Finish The Same Thing(In Place)


  • 0
    A

    For challenge myself, I try to use array to do the same thing (AC already)

    The key function is fnPartition, I use part of insertion sort to implement "in place",

        public ListNode Partition(ListNode head, int x)
        {
            int count = 0;
    
            ListNode temp = head;
            while (temp != null)
            {
                count++;
                temp = temp.next;
            }
    
            int[] input = new int[count];
            int index = 0;
            while (head != null)
            {
                input[index] = head.val;
                head = head.next;
                index++;
            }
    
            int[] ans = fnPartition(input, x);
    
    
            ListNode dummy = new ListNode(-1);
            ListNode curr = dummy;
            for (int i = 0; i < ans.Length; i++)
            {
                curr.next = new ListNode(ans[i]);
                curr = curr.next;
            }
    
            return dummy.next;
        }
    
        public int[] fnPartition(int[] array, int x)
        {
            //Part of Insertion Sort => O(n) = n^2
    
            int MoveCount = 0;
    
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] < x)
                {
                    int curr = i;
                    for (int j = 0; j < i - MoveCount; j++)
                    {
                        //swap
                        int temp = array[curr - 1];
                        array[curr - 1] = array[curr];
                        array[curr] = temp;
                        curr--;
                    }
                    MoveCount++;
                }
            }
    
            return array;
        }

Log in to reply
 

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