# My solution in Java O(n) time

• ``````//This question is much similar with that "Sort List"</body>
//1. split into 2 parts</hr>
//2. reverse 2nd list</hr>
//3. merge them

ListNode lnHalf=lnMiddle.next;
lnMiddle.next=null; // split into two list
lnHalf=reverse(lnHalf); // Reverse the 2nd list
}
public ListNode Merge(ListNode first, ListNode second){
Boolean flag=true;
while(first!=null && second!= null){
if (flag){
curr.next=first;
first=first.next;
flag=false;
}
else{
curr.next=second;
second=second.next;
flag=true;
}
curr=curr.next;
}
curr.next=(first==null)? second:first;
}//Merge

public ListNode reverse(ListNode n){
if(n==null || n.next==null) return n;
Stack<ListNode> lnStack=new Stack<ListNode>();
while(n!=null){
lnStack.push(n);
n=n.next;
}
n=lnStack.pop();
ListNode current=n;  // lnHalf is null right now.
while(!lnStack.isEmpty()){
current.next=lnStack.pop();
current=current.next;
}
current.next=null; // ** Very Important, or will return a infinite loop
return n;
}// reverse
public ListNode getMiddle(ListNode n){
ListNode slow,fast;
slow=fast=n;
while(fast.next!=null && fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}// getMiddle``````

• is this one in place? Actually I am not clear about what in place mean? Dose it mean not to create new Node or not to use other data structure?

• is this a O(n + 1/n) solution, since half of the list has been touched while reverse?

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