143. Reorder List

Today, I solved "Reorder List."

Description:

https://leetcode.com/problems/reorder-list/description/

It is hard to understand, but we are gonna reorder the list with rule. 

We can easily find the rule of the form:

Before: L0 -> L1 -> L2 -> L3 -> L4

After: L0 -> L4 -> L1 -> L3 -> L2

 

Now, how can we change the list order without changing the value?

We should make the other list to re-order the list. 

 

The recommendation is seperating the list as two lists.

Change the second list with reverse order. 

Merge them by connecting each other.

Solution:

To seperate as two lists, we should find the middle of the list. 

The first step:

"slow" pointer is on the head, and move one list.

"fast" pointer is on the next of the head, and move two lists.

 

The reason I set the loop while fast and fast.next:

We can have odd number of lists or even number of lists. 

fast.next would be the null if the number of the lists are even.

fast would be the null if the number of the lists are odd.

 

If the loop stops, we are gonna seperate two lists at the slow.next

It is not the middle when is the number of the list is even, but we can still use it. 

 

The Second step:

We are gonna make "prev" to make reverse! "tmp" is for the store the list temporarily.

For example, if the two lists like [1 -> 2] [3 -> 4] --> [1 -> 2] [3(prev) <- 4(second)]

 

"first" is the head of the first list. We also set second the last of the second list like this:

 [1(head) -> 2] [3(prev) <- 4(second)]

 

second.next is "3" in this case. We are gonna put 3 in tmp. And, second.next is now prev.

and second is now "4". prev is the list: [4 -> 3 ...]

 

The Last step:

In the last step, we are gonna merge the two list. [1, 2], [4, 3]

tmp1 and tmp2 stores the "2" and "4."

first.next = second ---> [1 -> 4]

second.next = tmp1 ---> [1 -> 4 -> 2]

first = tmp1 --->  2 is now new first.

second = tmp2 ---> 3 is now new second.

 

Time complexity: O(N)

Space complexity: O(1)