The title

Leetcode-cn.com/problems/pa… Determine if a linked list is palindromic. Is whether the first half is equal to the second half

Idea 1 — Dual Pointers

Use the fast or slow pointer to find the midpoint, then reverse the second half, and then compare it with the first half.

The fast pointer moves two steps at a time, and the slow pointer moves one step at a time. When the fast pointer is null, the slow pointer just reaches the midpoint

1, odd: exactly in the middle, even: in the middle after a position. So the latter list has to have no more than one element, or be the same length, so the comparison restriction is while(former list ==null)

There are more head elements than slow elements, so slow==null.

Code 1

public boolean isPalindrome(ListNode head) { ListNode fast = head,slow=head; while(fast ! = null && fast.next ! = null){ fast = fast.next.next; slow = slow.next; } slow = reverse(slow); fast = head; while(slow ! = null){ if(fast.val ! = slow.val){ return false; } slow = slow.next; fast = fast.next; } return true; } public ListNode reverse(ListNode slow){ ListNode a = slow,b = null; while(a ! = null){ ListNode temp = a.next; a.next = b; b = a; a = temp; } return b; }}Copy the code

Idea 2 – stack

The stack goes in first and then out, so you can compare the last half of the stack, which should be: linked list goes on the stack, record length, 1/2 element goes off the stack for comparison.

public boolean isPalindrome(ListNode head) { if(head == null){ return true; } Stack<Integer> s = new Stack(); int L = 0; ListNode temp = head; while(temp ! = null){ s.push(temp.val); temp = temp.next; L++; } L = L >>= 1; // for(int I = 0; int I = 0; i <= (L >>= 1); i++){ for(int i = 0; i <= L; i++){ if(head.val ! = s.pop()){ return false; } head = head.next; } return true; }}Copy the code