Reorder List

Q:Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

My Answer: using stack
1. find the end of the new list;
2. push the rest of the nodes into stack;
3. pop and merge nodes into the list;
(When dealing with linkedlist, always remember to break the link when necessary!!)

rl

Better Answer!
1. find the end of the new list and break the original list into two halves according to that node;
2. reverse the second list;
3. merge two lists;

oo

Remark:
Reverse a list:
reverse-list

Merge two lists:
merge-list-in-place

Pictures from here. A great place!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s