1. Find the middle point of the linked list using the fast and slow Pointers:

  • Assume a linked list head: 1->2-3->4->3->2->1;
  public ListNode findMiddle(ListNode head){
    ListNode fast = head;
    ListNode slow = head;
    while(fast! =null&&fast.next.next! =null){
      fast = fast.next.next;
      slow = slow.next;
    }
    
    return slow;// List midpoint;
    
  }
Copy the code
  • Look at the picture

2. Get the second half of the list:

  • Depending on the length of the list, there are two cases
  • If the list is even, the second half is slow
  • The length of the list is odd, and the last half is slow.next

To clarify: if the list is 1->2-3->4->3->2->1, the node that slow refers to is 4, so the last part of the node is slow. Next.

3. Reverse the second half of the list:

  • Reverse the result: slow becomes: 1->2->3

See: LeetCode 206

4. Pay the value of head to fast:

  • The value of fast is: 1->2-3->4->3->2->1;

Head = 1->2- >4->3->2->1;

5. Use the value of the fast or slow pointer.

 while(slow ! =null) {
    if(fast.val ! = slow.val) {return false;
     }
      fast = fast.next;
      slow = slow.next;
 }
 return true;
Copy the code

6. Thank you

  • Data structures and algorithms