# O(n) time and O(1) space 4ms java solution

• public class Solution {
return true;
}
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
if(fast != null && fast.next == null){
slow = slow.next;
}
ListNode rest = reverse(slow);
slow.next  = null;
while(fast != null && rest != null){
if(fast.val != rest.val){
return false;
}
fast = fast.next;
rest = rest.next;
}
return true;
}

}
return rest;
}
}

• Great solution! Yet it seems like the original linked list would not be a legal linked list anymore after the reverse() method, since that there will be 2 different objects both point to the last element of the newly reversed list. It would not do harm to the result of this question, yet it sounds kind of uncomfortable. I change it a little bit, by adding a node slow_prev pointing to the previous node of slow. Then I make slow_prev point to the last element of the former list before reversing. Here is my code:

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
int cnt = 1;
fast = fast.next.next;
slow = slow.next;
while (fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
slow_prev = slow_prev.next;
cnt++;
}
slow = f(slow);
slow_prev.next = slow;
while (cnt > 0)
{
if (fast.val != slow.val) return false;
fast = fast.next;
slow = slow.next;
cnt--;
}
return true;
}
private ListNode f(ListNode node)
{
if (node.next == null) return node; // one node left
ListNode last = f(node.next);
node.next.next = node;
node.next = null;
return last;
}
}

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