234.回文链表

234.回文链表

题目分析

• 中间节点：利用快慢指针，快指针每次走两步，慢指针每次走一步，当发现快指针的next或者next.next为空，意味着快指针已经走完链表，那么满指针正好位于中间位置
• 反转链表：熟记！！！
• 整体流程：
  • 走到中间结点:反转右边的链表
    
  • 分别从左边头结点和右边头结点开始,判断是否相等,当右边指向null时,中间结点要么被比较为相等,要么为奇数,一定为回文链表

Solution

    public boolean isPalindrome(ListNode head) {
    	if (head == null || head.next == null) return true; 
    	if (head.next.next == null) return head.val == head.next.val;
    	
    	// 找到中间节点
    	ListNode mid = middleNode(head);
    	// 翻转右半部分（中间节点的右边部分）
    	ListNode rHead = reverseList(mid.next);
    	ListNode lHead = head;
    	ListNode rOldHead = rHead;
    	
    	// 从lHead、rHead出发，判断是否为回文链表
    	boolean result = true;
    	while (rHead != null) {
    		if (lHead.val != rHead.val) {
    			result = false;
    			break;
    		}
    		rHead = rHead.next;
    		lHead = lHead.next;
    	}
    	
    	// 恢复右半部分（对右半部分再次翻转）
    	reverseList(rOldHead);
    	return result;
    }

    /**
     * 找到中间节点（右半部分链表头结点的前一个节点）
     * 比如 1>2>3>2>1中的3是中间节点
     * 比如 1>2>2>1中左边第一个2是中间节点
     * @param head
     * @return
     */
	private ListNode middleNode(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	
	/**
	 * 翻转链表
	 * @param head 原链表的头结点
	 * 比如原链表：1>2>3>4>null，翻转之后是：4>3>2>1>null
	 * @return 翻转之后链表的头结点（返回4）
	 */
	private ListNode reverseList(ListNode head) {
		ListNode newHead = null;
		while (head != null) {
			ListNode tmp = head.next;
			head.next = newHead;
			newHead = head;
			head = tmp;
		}
		return newHead;
	}

Reference：小码哥MJ