首页 > 其他 > 详细

Palindrome Linked List

时间:2015-07-19 13:12:02      阅读:163      评论:0      收藏:0      [点我收藏+]

Palindrome Linked List

问题:

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

思路:

  先选择中间的节点+反转链表

我的代码:

技术分享
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)    return true;
        
        ListNode mid = getMiddle(head);
        ListNode reverse = getReverse(mid);
        
        while(head!=null && reverse!=null)
        {
            if(head.val == reverse.val)
            {
                head = head.next;
                reverse = reverse.next; 
            }
            else return false;
        }
        
        return true;
        
    }
    public ListNode getMiddle(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode getReverse(ListNode head)
    {
        ListNode dummy = new ListNode(-1);
        while(head != null)
        {
            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }
}
View Code

 

反思:

  • 反转链表好久没写了,竟然都忘记了,代码果然好久没写就是不行啊,幸好在同学的指导下面又重新学会了。
  • palindrome的方法就是反转,从头开始反转,从中间反转,让反转后的等于前面的反转。

Palindrome Linked List

原文:http://www.cnblogs.com/sunshisonghit/p/4658404.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!