【java】234. Palindrome Linked List

问题原文点击打开链接

问题一开始的思路就是反转链表，但是如果直接对原始链表进行反转，而且不使用额外储存空间，是无法比较的。但是使用了额外的存储空间不符合题目要求的。所以最后的想法是，对链表后半段进行反转，将反转后的半段链表和前半段链表进行比较。代码如下

  //反转链表
    public ListNode reverse(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode next = head.next;
        head.next = null;
        while(next != null){
            ListNode tmp = next.next;
            next.next = head;
            head = next;
            next = tmp;
        }
        return head;
    }
    //获取链表的长度
    public int getLength(ListNode head){
        int length = 0;
        ListNode current = head;
        while(current != null){
            length++;
            current = current.next;
        }
        return length;
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null ||head.next == null) return true;
        int length = getLength(head);
        //找到需要开始反转的链表位置
        int revPos = length/2+1;
        ListNode search = head;
        while(revPos>1){
            revPos--;
            search = search.next;
        }
        search = reverse(search);
        while(search != null){
            if (search.val != head.val) return false;
            search = search.next;
            head = head.next;
        }
        return true;
    }