234. Palindrome Linked List.md

234. Palindrome Linked List

---

leetcode-cn Daily Challenge on October 23th, 2020.

---

Difficulty : Easy

Related Topics : LinkedList、Two Pointers

---

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:

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

---

Solution

• mine
  • Java

    • Runtime: 2 ms, faster than 40.17%, Memory Usage: 42.9 MB, less than 5.76% of Java online submissions

      // O(N)time
      // O(N)space
      public boolean isPalindrome(ListNode head) {
          LinkedList<ListNode> list = new LinkedList<>();
          while(head != null){
              list.add(head);
              head = head.next;
          }
          while(list.size() > 1){
              if(list.getLast().val == list.getFirst().val){
                  list.removeLast();
                  list.removeFirst();
              }else{
                  break;
              }
          }
          return list.size() < 2;
      }
      

    • Runtime: 1 ms, faster than 95.25%, Memory Usage: 41.8 MB, less than 5.76% of Java online submissions

      // O(N)time
      // O(1)space
      public boolean isPalindrome(ListNode head) {
          if(head == null || head.next == null) return true;
          ListNode p = head, q = head;
          while(p != null && p.next != null){
              p = p.next.next;
              q = q.next;
          }
          ListNode t = null;
          while(q != null){
              ListNode next = q.next;
              q.next = t;
              t = q;
              q = next;
          }
          while(head != null && t != null){
              if(head.val != t.val) return false;
              head = head.next;
              t = t.next;
          }
          return true;
      }
      

---