LeetCode 143
1.LinkedList
The problem can be divided by three steps:
Find the middle elements with two pointers
Reverse the right part by using 3 pointers, we can use the fast pointer before to save more space.
Merge two linked list, check whether the right part have the next node.
2.Array
The problem can be tackled in these ways
With Time O(n) and Space O(n)
Make a new array and get the elements from the old array
With Time O(n) and Space O (1)
This method requires a special input. Because we know the destination of every element in the array, we can iterate elements by doing these steps:
Get the current index from 1 because index 0 element never moves.
Find the target index and save the value in temp.
Put the current element in the target index.
Get the target index of temp index and repeat.
If the index has been set, go to the next one until it touches the end of the array.
This method needs a special input, for example if all elements in the array are positive, we can set them to negative to record that this element has been iterated.
The method to find the target index is
middleIndex = array.count/2
if(index <= middleIndex)
targetIndex = 2 index;
else
targetIndex = 2*array.count - 2*index -1With Time O(nlogn) and Space O (1)
This method can be divided into these steps:
Find the middle pair, move them to the last two position, move all the element behind the middle pair one forward.
Repeat this step until there is only two elements left in the left part.