leetcode：234. Palindrome Linked List

这个题目非常好。http://blog.csdn.net/u012249528/article/details/47124771给出了三种解法，其中前两个是不满足条件的，不过具有参考价值：

第一种办法：用数组倒着存前半段的链表的值，然后和后半段链表的值进行比较。这种解法运行的时间最久可能是因为数组倒着插入比较耗时。

第二种解法：在第一种的思路的基础上，我们要实现一个倒序，我们干嘛不用现成的数据结构-栈，于是把链表前半段压栈，然后出栈和后面的链表依次比较，这种运行时间最短，但因为用到了栈还是不符合题目要求。

第三种：我们这样想，我们可不可以不借助外在的存储实现倒序呢，其实是可以的，链表反转的时候我们就没有借助外在存储。思路是把后半段的原地链表反转然后和前半段进行比较（当然你也可以反转前半段）运行时间稍微比第二种慢一些，但是符合题目O（1）空间复杂度的要求

本题解决代码参考：https://discuss.leetcode.com/topic/33376/java-easy-to-understand

    public boolean isPalindrome(ListNode head) {

        ListNode slow = head;

        ListNode fast = head;

        if(head==null||head.next==null){

            return true;

        }

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        if (fast != null) { // odd nodes: let right half smaller 不用貌似也行

            slow = slow.next;

        }

        //对后半段反转

        slow = reverse(slow);

        fast = head;

        while(slow!=null){

            if(fast.val!=slow.val){

                return false;

            }

            fast = fast.next;

            slow = slow.next;

        }

        return true;

    }

    public ListNode reverse(ListNode head){

        ListNode pre = null;

        while(head != null){

            ListNode tmp = head.next;

            head.next = pre;

            pre = head;

            head = tmp;

        }

        return pre;

    }

巴特西

leetcode：234. Palindrome Linked List

最新文章

热门文章