[LC 234]. Palindrome Linked List

算法好想,先找出整个list的长度,然后找到mid pointer,反转前半个list,以mid point为出发点同时向左右两个方向比较node的val。

写出clean code并不是很容易。以下是一个比较clean的版本,学习一下。用slow和fast两个pointer找mid point,fast速度是slow的二倍,在找mid point的同时反转前半个list。

    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode p1 = head; // slow, left part start
        ListNode p2 = head; // fast
        ListNode p3 = p1.next; // right part start
        ListNode pre = p1;
        
        // find mid pointer, reverse left part
        while (p2.next != null && p2.next.next != null) {
            p2 = p2.next.next;
            pre = p1; 
            p1 = p3;
            p3 = p3.next;
            p1.next = pre;
        }
        
        // for odd length, left more p1
        if (p2.next == null) {
            p1 = p1.next;
        } else { // even length, do nothing
            
        }
        
        while (p1 != null && p3 != null) {
            if (p1.val != p3.val) return false;
            p1 = p1.next;
            p3 = p3.next;
        }
        
        return true;
        
    }

Tip: 1. 11 – 13行,当需要更新多个pointer时,尝试从最左到最右依次更新,以避免出错。
2. 19行,注意此时前半个list已经反转,所以p1 move left是p1.next不是p3.

可以交流是否需要保持原输入list不变,如果需要,还要在后面比较的过程中还原输入。不过在以上code基础上修改就会比较难看。

   public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode p1 = head; 
        ListNode p2 = head;
        ListNode p3 = p1.next; 
        ListNode pre = p1;
        
        while (p2.next != null && p2.next.next != null) {
            p2 = p2.next.next;
            pre = p1;
            p1 = p3;
            p3 = p3.next;
            p1.next = pre;
        }
        
        ListNode next = p3;    // restore
        if (p2.next == null) {
            ListNode tmp = p1; // 
            p1 = p1.next;
            tmp.next = p3;     // 
            next = tmp;        // 
        } 

        while (p1 != null && p3 != null) {
            if (p1.val != p3.val) return false;
            ListNode tmp = p1; //
            p1 = p1.next;
            p3 = p3.next;
            tmp.next = next;   // 
            next = tmp;        // 
        }

        return true; 
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s