# Java solution with 3 steps

• This question is a combination of Reverse a linked list I & II. It should be pretty straight forward to do it in 3 steps :)

``````public void reorderList(ListNode head) {

//Find the middle of the list
while(p2.next!=null&&p2.next.next!=null){
p1=p1.next;
p2=p2.next.next;
}

//Reverse the half after middle  1->2->3->4->5->6 to 1->2->3->6->5->4
ListNode preMiddle=p1;
ListNode preCurrent=p1.next;
while(preCurrent.next!=null){
ListNode current=preCurrent.next;
preCurrent.next=current.next;
current.next=preMiddle.next;
preMiddle.next=current;
}

//Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
p2=preMiddle.next;
while(p1!=preMiddle){
preMiddle.next=p2.next;
p2.next=p1.next;
p1.next=p2;
p1=p2.next;
p2=preMiddle.next;
}
}``````

• ``````public class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast!= null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
if (fast != null){
slow = slow.next;
fast.next = null;
}
slow = reverseList(slow);
while(slow != null){
ListNode nextSlow = slow.next;
slow.next = fast.next;
fast.next = slow;
fast = slow.next;
slow = nextSlow;
}
}

public ListNode reverseList(ListNode head){
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
}
}
}
``````

May I know why my code gives memory limit excess error? Thanks.

• This is cool!

• Thank you!!!

• @BroLegend you are not breaking the link between the first half and the second half of the list.

• quite elegant!

• Thank you! Woww it is my post last year, thanks to Leetcode, I got my dream job!

• quite smart! how about your job:D

• Haha, my job is great! There are a lot of smart people here, its mission is make transportation as reliable as running water~~~

• same here, just breaking down into methods for clarity (C#)

``````    public void ReorderList(ListNode head)
{
if (head == null) return;
}

public ListNode Split(ListNode head)
{
ListNode slow = head;
ListNode fast = head.next;

while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}

ListNode head2 = slow.next;
slow.next = null;
}

public ListNode Reverse(ListNode head)
{
ListNode curr = head;
ListNode prev = null;

while (curr != null)
{
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

return prev;
}

{
ListNode curr1 = head1;
ListNode curr2 = head2;

while (curr1 != null && curr2 != null)
{
ListNode next1 = curr1.next;
ListNode next2 = curr2.next;

curr1.next = curr2;
curr2.next = next1;

curr1 = next1;
curr2 = next2;
}

}
``````

• thanks. It's a nice solution.

• @wanqing Nice and simple with clear explanation!

• @jdrogin Clean bro, clean

1. Find the part2;
2. reverse part2;
3. append one by one;
``````	public void reorderList(ListNode head) {
if(head == null) return;

ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}

ListNode part2 = new ListNode(-1);
ListNode node = slow.next;
slow.next = null;
part2.next = node;
while(node != null && node.next != null){
ListNode next = node.next;
node.next = next.next;
next.next = part2.next;
part2.next = next;

}

ListNode node1 = head;
ListNode node2 = part2.next;
while(node2 != null){
ListNode next1 = node1.next;
ListNode next2 = node2.next;
node1.next = node2;
node2.next = next1;
node1 = next1;
node2 = next2;
}
}``````

• My CPP code:

``````
{
return;
ListNode **p = &head, **q = &head;
while (*q && (*q)->next)
{
p = &(*p)->next;
q = &(*q)->next->next;
}
for (q = &(*p)->next; *q; swap(*p, *q))
swap(*p, (*q)->next);
for (q = &head->next; *p != *q; q = &(*q)->next->next)
{
swap(*p, *q);
swap(*p, (*q)->next);
}
}
```
part of the code is from @StefanPochmann 's answer for Reverse Linked List II.

https://discuss.leetcode.com/topic/45392/6-10-lines-in-c```

• I use stack to store the ListNode but system return: The Limite Exceeded.
could you point out what wrong with my code.I would thank you for you help.
my code:

``````/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
Stack<ListNode> stack=new Stack();
int length=0;
while(cur!=null){
stack.push(cur);
cur=cur.next;
length++;
}
if(length==2) return;
while(cur!=stack.peek()){
ListNode tmp=cur.next;
cur.next=stack.pop();
cur.next.next=tmp;
cur=tmp;
}
}
}``````

• @wanqing , do you know why I got `Memory Limit Exceeded` if replace your third reverse logic(Reverse the half after middle ) to the following function?

``````public ListNode merge(ListNode head1, ListNode head2)
{
ListNode curr1 = head1;
ListNode curr2 = head2;

while (curr1 != null && curr2 != null)
{
ListNode next1 = curr1.next;
ListNode next2 = curr2.next;

curr1.next = curr2;
curr2.next = next1;

curr1 = next1;
curr2 = next2;
}

}
``````

• @BroLegend you can add "fast.next = None" after the while loop"

• @BroLegend
based on his solution, write Python code:

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: void Do not return anything, modify head in-place instead.
"""
return

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

tmp = slow.next
slow.next = None
slow = tmp

while slow:
tmp = slow.next
slow.next = cur.next
cur.next = slow
cur = slow.next
slow = tmp

prev = None

while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
``````

• My code is similar to yours.

``````public class Solution {
public void reorderList(ListNode head) {
ListNode helper = new ListNode(0);
ListNode fast = helper;
ListNode slow = helper;

while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}

ListNode tail = reverse(slow.next);
slow.next=null;
//return helper.next;
}

private ListNode reverse(ListNode x){
ListNode start = null;
while(x!=null){
ListNode next = x.next;
x.next = start;
start = x;
x = next;
}
return start;
}
private void merge(ListNode x, ListNode y){

while(y!=null){
ListNode xn = x.next;
ListNode yn = y.next;
x.next = y;
y.next = xn;
x=xn;
y=yn;
}
}
}
``````

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