Dada una lista enlazada individualmente, determine si es un palíndromo.
Solución Java 1: cree una nueva lista invertida
Podemos crear una nueva lista en orden inverso y luego comparar cada nodo. El tiempo y el espacio son O (n).
public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode p = head; ListNode prev = new ListNode(head.val); while(p.next != null){ ListNode temp = new ListNode(p.next.val); temp.next = prev; prev = temp; p = p.next; } ListNode p1 = head; ListNode p2 = prev; while(p1!=null){ if(p1.val != p2.val) return false; p1 = p1.next; p2 = p2.next; } return true; } |
Solución Java 2: romper y revertir la segunda mitad
Podemos usar un puntero rápido y lento para obtener el centro de la lista, luego invertir la segunda lista y comparar dos sublistas. El tiempo es O (n) y el espacio es O (1).
public boolean isPalindrome(ListNode head) { if(head == null || head.next==null) return true; //find list center ListNode fast = head; ListNode slow = head; while(fast.next!=null && fast.next.next!=null){ fast = fast.next.next; slow = slow.next; } ListNode secondHead = slow.next; slow.next = null; //reverse second part of the list ListNode p1 = secondHead; ListNode p2 = p1.next; while(p1!=null && p2!=null){ ListNode temp = p2.next; p2.next = p1; p1 = p2; p2 = temp; } secondHead.next = null; //compare two sublists now ListNode p = (p2==null?p1:p2); ListNode q = head; while(p!=null){ if(p.val != q.val) return false; p = p.next; q = q.next; } return true; } |
Solución Java 3: recursivo
public class Solution { ListNode left; public boolean isPalindrome(ListNode head) { left = head; boolean result = helper(head); return result; } public boolean helper(ListNode right){ //stop recursion if (right == null) return true; //if sub-list is not palindrome, return false boolean x = helper(right.next); if (!x) return false; //current left and right boolean y = (left.val == right.val); //move left to next left = left.next; return y; } } |
El tiempo es O (n) y el espacio es O (n).
