编写一个函数,检查输入的链表是否是回文的。

示例 1:

输入: 1->2
输出: false 

示例 2:

输入: 1->2->2->1
输出: true 

分析找出链表的中间结点,将中间结点以后的结点逆置,比较原链表和逆置后的链表即可得出结果
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    if(head==NULL )
        return 1;
    while(fast && fast->next)//这部分很简单,找出中间结点 
    {
        slow=slow->next;
        fast=fast->next ->next;
    }

    struct ListNode* prev=NULL;
    struct ListNode* mid=slow;
    struct ListNode* end=NULL;    
    while(mid)//这部分是逆置,在这走了不少弯路,
                //如果按照三个指针岔开的方法即NULL,slow,slow->next,很容易出现空指针出错
                //这种方法将后两个指针步进一致巧妙避免了这个问题,或者将逆置单独写在函数也可以避免。 
    {
        end=mid->next;
        mid->next=prev;
        prev=mid;
        mid=end;
    }
    
    while(head && prev)//比较部分也很简单,逆置后的表头是prev,
                       //因为逆置后的表尾(原中间结点)next被置为NULL,
                       //所以不用关心原表奇数偶数只要出现NULL就可以结束比较 
    {
        if(head->val!=prev->val)
        {
            return 0;
        }
        head=head->next;
        prev=prev->next;
    }
    return 1;
}

 

上一篇:剑指 Offer 24. 反转链表(leetcode)


下一篇:锁相关