153-判断回文链表(两种方法)

r囧r小猫 2023-01-11 09:15 85阅读 0赞

**题目如下：**  
请判断一个链表是否为回文链表。  
输入: 1->2  
输出: false

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

## 解题方法1 ##

1、定义快指针和慢指针，初始化均指向头结点  
2、while (fast->next != NULL && fast->next->next != NULL)，快慢指针一起往后走，直到退出while循环，此时的慢指针slow指向整条链表的中间结点，我们把这个中间结点当做前半段链表的尾结点  
3、 ListNode \*r = slow->next;//r指向后半段链表的头结点  
4、 slow->next = NULL;//将前半段链与后半段链断开  
5、将后半段链表进行逆置  
6、将前半段链表的val值与后半段链表的val值一一比较，如果对比遇到值不相同则执行return false;如果两段链表对应的val值均相同，最后执行return true;

bool isPail(ListNode *head)
    {
        
        if (head == NULL || head->next == NULL)
        {
        
            return true;
        }
        ListNode *fast = head;//定义快指针，初始化指向头结点 
        ListNode *slow = head;//定义慢指针，初始化指向头结点 
        while (fast->next != NULL && fast->next->next != NULL)
        {
        
            fast = fast->next->next;
            slow = slow->next;
        }
        //此时slow指向的就是前半段链表的尾结点 
        
        ListNode *r = slow->next;//r指向后半段链表的头结点 
        slow->next = NULL;//将前半段链与后半段链断开 
        ListNode *p = NULL;
    	ListNode *s=NULL;
        while (r != NULL)//将后半段链表进行逆置 
        {
        
            s = r->next;
            r->next = p;
            p = r;
            r = s;
        }
        r = p; 
        while (r != NULL && head != NULL)//将前半段链表的值与后半段链表的值一一对比 
        {
        
            if (r->val != head->val)
            {
        
                return false;
            }
            head = head->next;
            r = r->next;
        }
        return true;
    }

代码运行图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 解题方法2 ##

**使用双端队列解决问题**

bool isPail(ListNode *head)
    {
        
        if (head == nullptr || head->next == nullptr)
        {
        
            return true;
        }
        deque<int> q;
        while(head!=nullptr)
        {
        
            q.push_back(head->val);//尾部添加数据 
            head = head->next;//遍历传入的链表 
        }
        while(q.size() > 1)//将双端队列的头尾数据值进行比较 
        {
        
            if(q.front() != q.back())//数据值不相同直接返回false 
                return false;
            q.pop_back();//尾部移除一个数据 
            q.pop_front();//头部移除一个数据 
        }
        return true;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/f1712b509ba943c3901c0969b8c3823f.png