（Java）leetcode-234 Palindrome Linked List

淡淡的烟草味﹌ 2022-02-25 07:31 109阅读 0赞

# 题目 #

【判断回文链表】  
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?

根据提交结果，这里还应该加上一个例子：  
Input: 1->2->3->2->1  
Output: true

# 思路 #

将链表的后半部分进行翻转，成为一个新链表，然后判断这两个链表的值是否相等，相等即为回文链表。  
时间复杂度O(n)  
由于只使用了三个指针，时间复杂度为O(1)

# 代码1 #

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isPalindrome(ListNode head) { 
            ListNode fast = head, slow = head;
            while(fast != null && fast.next != null  ){ 
            	fast = fast.next.next;
            	slow = slow.next;
    
            }
            //特殊处理
            if(fast != null){ 
            	slow = slow.next;
            }
            //下面对后半段进行迭代法翻转
      
            ListNode newHead = null;
            
            
            while(slow != null){ 
            fast = slow.next; //把fast指向工作指针的下一个地址防止丢失
            slow.next = newHead; //指向新表头
            newHead = slow;
            slow = fast;       
            }
    
            //下面比较两个链表是否相同
            while(newHead != null){ 
            	if(head.val != newHead.val) return false;
            	head = head.next;
            	newHead = newHead.next;
            }
            return true;
        }
    }

## 提交结果 ##

Runtime: 1 ms, faster than 93.53% of Java online submissions for Palindrome Linked List.  
Memory Usage: 42.6 MB, less than 31.50% of Java online submissions for Palindrome Linked List.