leetcode 234. Palindrome Linked List

Seawolf

1. Given a singly linked list, determine if it is a palindrome.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: 1->2
   
6. Output: false
   
7. Example 2:
   
8. 
   
9. Input: 1->2->2->1
   
10. Output: true
    
11. Follow up:
    
12. Could you do it in O(n) time and O(1) space?

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. class Solution {
   
10.     public boolean isPalindrome(ListNode head) {
    
11.         List<Integer> list = new ArrayList<>();
    
12.         while(head != null){
    
13.             
    
14.             list.add(head.val);
    
15.             head = head.next;
    
16.         }
    
17.         
    
18.         int start = 0;
    
19.         int end = list.size()-1;
    
20.         while(end - 1 >= start){
    
21.             if(!list.get(start).equals(list.get(end))) return false;
    
22.             
    
23.             end--;
    
24.             start++;
    
25.         }
    
26.         
    
27.         return true;
    
28.     }
    
29. }

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. class Solution {
   
10.     public boolean isPalindrome(ListNode head) {
    
11.         if(head == null || head.next == null) return true;
    
12.         ListNode slow = head;
    
13.         ListNode fast = head;
    
14.         
    
15.         while(fast != null && fast.next != null){
    
16.             fast = fast.next.next;
    
17.             slow = slow.next;
    
18.         }
    
19.         
    
20.         fast = head;
    
21.         int length = 0;
    
22.         while(fast != null) {
    
23.             length++;
    
24.             fast = fast.next;
    
25.         }
    
26.         
    
27.         fast = head.next;
    
28.         head.next = null;
    
29.         while(fast != slow){
    
30.             ListNode temp = fast.next;
    
31.             fast.next = head;
    
32.             head = fast;
    
33.             fast = temp;
    
34.         }
    
35.         
    
36.         if(length % 2 != 0) slow = slow.next;
    
37.         
    
38.         while(head!= null && slow!= null){
    
39.             if(head.val != slow.val) return false;
    
40.             
    
41.             head = head.next;
    
42.             slow = slow.next;
    
43.         }
    
44.         
    
45.         return true;
    
46.     }
    
47. }

复制代码