LeetCode 234——回文链表

1. 题目

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false
示例 2:

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2. 思路

• 此题可以看做是反转链表 和 链表中间结点 的结合。

定义快慢两个指针，寻找中间结点，同时在慢指针移动的过程中反转前半部分子链表。当找到中间结点时，再分别向前向后比较前后两个子链表的每一个结点值是否相同。

• 偶数结点情况如下

  
  3.png

4.png 5.png 6.png

• 此时，我们分别得到了以 slow 为头指针的前半部分子链表和以 p2 为头指针的后半部分子链表。由于中间结点偏向后边，所以我们需要先比较最中间的两个结点（此处为 2 和 3 结点），然后再依次向两边循环比较直到到达子链的链尾。

• 再来看奇数结点的情况

7.png 8.png

• 奇数个结点时，我们依然可以分别得到以 slow 为头指针的前半部分子链表和以 p2 为头指针的后半部分子链表。此时，由于 slow 指向的中间结点无须比较，我们只需从 slow 后面第一个结点和 p2 指向的结点开始循环向两边比较即可（此处为 2 和 4 结点）。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        if (head == NULL || head->next == NULL)     // 空链或只有一个结点，返回 true
        {
            return true;            
        }
        
        else
        {
            /* 此为反转链表的三个指针，slow 即代表 p1 */
            ListNode* slow = head;           // 慢指针指向第一个结点
            ListNode * p2 = slow->next;      // 第二个结点
            ListNode * p3 = p2->next;        // 第三个结点
            
            ListNode* fast = head;           // 快指针指向头结点

            // 奇数结点快指针指向最后一个结点结束
            // 偶数结点快指针指向 NULL 结束
            while(fast && fast->next)   
            {
                p3 = p2->next;
                fast = fast->next->next;    // 快指针前进两步
                p2->next = slow;            // 反转链表
                slow = p2;                  // 慢指针前进一步
                p2 = p3;
            }

            head->next = NULL; // 处理前半部分子链的尾节点

            // 偶数结点
            if(!fast)
            {
                // 先比较 slow 后的两个结点是否相同
                if (slow->val == slow->next->val)
                {
                    // 以 slow 后的第三个结点和 p2 指向的结点开始循环向两边比较
                    slow = slow->next->next;
                    while(slow)
                    {
                        if (slow->val != p2->val)
                        {
                            return false;
                        }
                        else
                        {
                            slow = slow->next;
                            p2 = p2->next;
                        }
                    }
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 奇数结点
            else
            {
                // 以 slow 后的第一个结点和 p2 指向的结点开始循环向两边比较
                slow = slow->next;
                while(slow)
                {
                    if (slow->val != p2->val)
                    {
                        return false;
                    }
                    else
                    {
                        slow = slow->next;
                        p2 = p2->next;
                    }
                }
                return true;
            }
        }
                
    }
};

获取更多精彩，请关注「seniusen」!

seniusen