Monday, January 11, 2016

Palindrome Linked List - Leetcode Java | Welkin Lan

Palindrome Linked List – Leetcode Java | Welkin Lan
Given a singly linked list, determine if it is a palindrome.
Could you do it in O(n) time and O(1) space?
1. reverse the second half
2. compare 1 with the first half
https://leetcode.com/discuss/78152/java-easy-to-understand
return true;
}
while (runner != null && runner.next != null) {
walker = walker.next;
runner = runner.next.next;
}
return false;
}
}
return true;

}

private ListNode reverse(ListNode cur) {
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
https://leetcode.com/discuss/44751/11-lines-12-with-restore-o-n-time-o-1-space
Reversed first half == Second half?
Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.
Same as the above, but while comparing the two halves, restore the list to its original state by reversing the first half back.

```    public boolean isPalindrome(ListNode head) {
return true;
}

middle.next = reverse(middle.next);

ListNode p1 = head, p2 = middle.next;
while (p1 != null && p2 != null && p1.val == p2.val) {
p1 = p1.next;
p2 = p2.next;
}

return p2 == null;
}

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

return slow;
}

ListNode prev = null;

}

return prev;
}```
https://leetcode.com/discuss/50575/short-accepted-cpp-code
public boolean isPalindrome(ListNode head) { if(head==null) return true; ListNode fast = head; ListNode slow = head; ListNode pre=null; ListNode next = null; while(fast!=null&&fast.next!=null){ fast = fast.next.next;// 此步一定要在链表逆转操作之前执行 next = slow.next; slow.next = pre; pre = slow; slow = next; } if(fast!=null&&fast.next==null){ // 表示链表长度为奇数，则从中间节点的下一节点开始比较 slow = slow.next; } while(pre!=null&&slow!=null){ if(pre.val!=slow.val) return false; pre = pre.next; slow = slow.next; } return true; }
http://www.cnblogs.com/theskulls/p/4940695.html

```    public boolean isPalindrome(ListNode head) {
ArrayList<Integer> list = new ArrayList<Integer>();
return true;
while(p.next != null){
ListNode tmp = new ListNode(p.next.val);
tmp.next = prev;
prev = tmp;
p = p.next;
}
ListNode p2 = prev;
while(p1!=null){
if(p1.val != p2.val)
return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}```
https://leetcode.com/discuss/49428/concise-o-n-o-n-java-solution-without-reversing-the-list
Since it's a recursive algorithm, it uses O(N) space.

Every Node compared twice,add another flag to mark it can improve it.
public ListNode root; public boolean isPalindrome(ListNode head) { root = head; return (head == null) ? true : _isPalindrome(head); } public boolean _isPalindrome(ListNode head) { boolean flag = true; if (head.next != null) { flag = _isPalindrome(head.next); } if (flag && root.val == head.val) { root = root.next; return true; } return false; }

In order to apply this approach, we first need to know when we've reached the middle element, as this will form our base case. We can do this by passing in length - 2 for the length each time. When the length equals 0 or 1, we're at the center of the linked list. This is because the length is reduced by 2 each time. Once we've recursed Yi times, length will be down to 0.
public static class Result {
public boolean result;
public Result(LinkedListNode n, boolean res) {
node = n;
result = res;
}
}

if (head == null || length <= 0) { // Even number of nodes
} else if (length == 1) { // Odd number of nodes
}

/* Recurse on sublist. */
Result res = isPalindromeRecurse(head.next, length - 2);

/* If child calls are not a palindrome, pass back up
* a failure. */
if (!res.result || res.node == null) {
return res;
}

/* Check if matches corresponding node on other side. */

/* Return corresponding node. */
res.node = res.node.next;

return res;
}

public static int lengthOfList(LinkedListNode n) {
int size = 0;
while (n != null) {
size++;
n = n.next;
}
return size;
}

return p.result;
}

Stack<Integer> stack = new Stack<Integer>();

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

/* Has odd number of elements, so skip the middle */
if (fast != null) {
slow = slow.next;
}

while (slow != null) {
int top = stack.pop().intValue();
if (top != slow.data) {
return false;
}
slow = slow.next;
}
return true;
}
}

while (node != null) {
node = node.next;
}
}

while (one != null && two != null) {
if (one.data != two.data) {
return false;
}
one = one.next;
two = two.next;
}
return one == null && two == null;
}
https://leetcode.com/discuss/45309/reversing-a-list-is-not-considered-o-1-space