LeetCode:234. Palindrome Linked List 回文链表（C语言）

た入场券 2023-06-19 11:20 15阅读 0赞

**题目描述：**  
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2  
输出: false

示例 2:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/palindrome-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    bool isPalindrome(struct ListNode* head)
    { 
        //处理特殊情况
        if(head == NULL || head->next == NULL)
        { 
             return true;
        }
        if(NULL == head->next->next)
        { 
            if(head->val == head->next->val)
            { 
                return true;
            }
            else
            { 
                return false;
            }
        }
    
        struct ListNode *pfast = NULL; //快指针
        struct ListNode *pslow = NULL; //慢指针
    
        //将快指针定位到链表尾部最后一个节点（若奇链表）或倒数第二个节点（若偶链表），慢指针定位到链表中部
        pfast = head;
        pslow = head;
        
        while(pfast && pfast->next != NULL)
        { 
            pfast = pfast->next->next;
            pslow = pslow->next;
        }
    
        //将链表中部之前的节点反转
        struct ListNode *ppre = NULL;
        struct ListNode *pnext = NULL;
        
        while(pslow != head)
        { 
            pnext = head->next;
            head->next = ppre;
            ppre = head;
            head = pnext;
        }
    
        //若是奇链表
        if(pfast != NULL && pfast->next == NULL)
        { 
            pslow = pslow->next;
        }
    
        while(ppre != NULL)
        { 
            if(ppre->val != pslow->val)
            { 
                return false;
            }
            ppre = ppre->next;
            pslow = pslow->next;
        }
        return true;
    }

**运行结果：**  
![在这里插入图片描述][20191206120335724.png]  
**Notes：**  
使用快慢指针，快指针每次两个步长后移，慢指针每次一个步长后移，这样当快指针走到尾部时，慢指针刚好走到中部，然后将前半段链表反转和后半段链表进行对比。

[20191206120335724.png]: https://img-blog.csdnimg.cn/20191206120335724.png