Palindrome Linked List

问题描述：判断一个单链表是否是回文，即正着读和反向读是一样的

问题分析：采用c语言书写，首先找到链表的中间节点，然后将中间节点以后的反转，比较两个半链表是否一样。

struct ListNode {
      int val;
      struct ListNode *next;
  };
//找中间节点，利用快指针和慢指针来控制
struct  ListNode* getMid(struct ListNode* head)
    {// at least two nodes
      struct  ListNode* slow = head;
      struct  ListNode* fast = head;
      struct ListNode* preslow = head;
      //控制偶数链表时返回中间的第二个节点
      while(fast!=NULL&&fast->next!=NULL){
           fast=fast->next->next;
           preslow = slow;  
           slow = slow->next;

       }
        preslow->next = NULL;

        return slow;
    }
//反转链表    
 struct ListNode* reverse(struct ListNode* head)
    {
        if(head == NULL || head->next == NULL)
            return head;
        else if(head->next->next == NULL)
        {// two nodes
            struct ListNode* tail = head->next;
            head->next = NULL;
            tail->next = head;
            return tail;
        }
        else
        {
            struct ListNode* pre = head;
            struct ListNode* cur = pre->next;
            pre->next = NULL;   // set tail
            struct ListNode* post = cur->next;
            while(post)
            {
                cur->next = pre;
                pre = cur;
                cur = post;
                post = post->next;
            }
            cur->next = pre;
            return cur;
        }
    }

bool isPalindrome(struct ListNode* head) {
    if(head==NULL||head->next==NULL) return true;

    struct ListNode*mid,*h1,*h2;
    mid = getMid(head);

    h2 = reverse(mid);

    h1 = head;

    while(h1&&h2){
        if(h1->val!=h2->val)
            return false;
        else{
            h1 = h1->next;
            h2 = h2->next;
        }
    }

    return true;

}