LeetCode 234 Palindrome Linked List

/**
 * @Description 链表类需要自定义
 * @Date 2019/8/11 17:40
 **/
class ListNode
{
    int val;
    ListNode next;

    public ListNode(int x){
        val=x;
    }

}

/**
 * @Description
 * @Date 2019/8/11 17:40
 **/
public class PalindromeLinkedList {

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;

        // 直到快指针到达最后一个节点（链表长度为奇数时）或者刚刚跳出最后一个节点为止（链表长度为偶数时）
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // 如果链表的长度是奇数，则这个if块会让慢指针跳过正中间的那个节点
        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null) {
            if (slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }

        return true;
    }

    @Test
    public void test() {

        // ListNode listNode = new ListNode("abccba");
        // String
        // ListNode listNode = new ListNode();

        ListNode head = new ListNode(1);//创建头节点
        head.next = new ListNode(2);//再定义头节点的next域
        head.next.next = new ListNode(3);//再定义头节点的next域
        ListNode t = head.next.next;
        for(int i=4;i<=6;i++) {//创建一个简单的链表{1,2,3,4,5,...,9}
            t.next = new ListNode(7-i);
            t = t.next;
        }
        printListNode(head);
        System.out.println();
        System.out.println(isPalindrome(head));

    }
}