## Question

Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

Example:

``````

``````

## Thought Process

1. Reversed
1. By reversing the second half of the list, we can compare the list node by node
2. Time complexity O(n)
3. Space complexity O(1)

## Solution

``````class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l1r = reverse(l1), l2r = reverse(l2);
ListNode cur = new ListNode(0);
int sum = 0;
while (l1r != null || l2r != null) {
if (l1r != null) {
sum += l1r.val;
l1r = l1r.next;
}
if (l2r != null) {
sum += l2r.val;
l2r = l2r.next;
}
cur.val = sum % 10;
sum /= 10;
}
return cur.val == 0 ? cur.next : cur;
}

private ListNode reverse(ListNode node) {
ListNode dummy = new ListNode(-1), next;
while (node != null) {
next = node.next;
node.next = dummy.next;
dummy.next = node;
node = next;
}
return dummy.next;
}
}
``````
``````class Solution {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reversed = reverse(slow);
reversed = reversed.next;
}
}

public ListNode reverse(ListNode node) {
ListNode dummy = new ListNode(-1), next;
while (node != null) {
next = node.next;
node.next = dummy.next;
dummy.next = node;
node = next;
}
return dummy.next;
}
}
``````