【算法刷题】链表篇-链表的回文结构

题目要求

链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

1 -> 2 -> 3 -> 2 -> 1

1 -> 2 -> 2 -> 1

上面两个是回文结构

方法1：思路

1.遍历链表，把结点对应的值放到数组中。
未知数组的大小
- 法1：直接设置900个空间(题目中已经说明链表长度小于等于900)
- 法2：遍历链表求出链表的长度，然后再对应开辟数组 ->效率低，不选用
2.判断链表回文->转化成判断数组元素是回文的
- 双指针
- 定义头尾指针进行比较，left指针指向最左边，right指针指向最右边。二者指向的元素比较
  - a[left] = a[right] ==> left++ right--
  - a[left] != a[right] ==> return false
- 循环结束条件：left < right (不取等，当二者指向相同的元素/left > right 说明已经是回文结构了)
- 若比较完成，退出循环，说明是回文结构。
时间复杂度：0(N)

图解

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //空链表==>不是回文结构
        if(A == NULL)
        {
            return false;
        }
     //存放到数组中
      int arr[900];//题目说了，链表长度小于等于900
      int sz = 0;//标志数组元素
      //遍历链表，存放元素到数组中
      struct ListNode* curA = A;
      while(curA)
      {
         //放到sz位置上，然后sz++
         arr[sz++] = curA->val;
          //curA指向下一个结点
         curA = curA->next;
       }
      //对数组元素进行判断是否是回文结构
       int left = 0;
       int right = sz - 1;//最后一个元素
        while(left < right)
        {
            if(arr[left] != arr[right])
            {
                return false;
            }
            left ++;
            right --;
        }
        //数组元素比较完成，说明数组是回文结构  -> 链表是回文的
        return true;
    }
};

方法2

1.找到链表的中间结点(使用快慢指针)，记为mid
2.将mid到尾结点部分链表进行反转 (使用三指针n1,n2,n3)，返回新的头记为rhead
- n1:初始化为空 ,n2反转要指向的结点
- n2:要反转的结点
- n3:保存n2的下一个结点，防止找不到
3.遍历比较[head,rhead)结点和 [rhead,尾结点] 结点
- 为了保留两个头结点位置，定义新的变量进行遍历，
- curA 遍历[head,rhead] curR 遍历[rhead,尾结点]
- 如果curA和curB指向结点的值不相同 ->不是回文
循环结束条件：curA 或者curB其中一个为空 (curA && curB)
能跳出循环，说明curA和curB指向的值全都相等 ->是回文

图解：

偶数个结点
奇数个结点
非回文

注意：反转之前的mid的前一个结点的next仍指向原来的位置

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

//找链表的中间结点 - 快慢指针
struct ListNode* MidNode(struct ListNode* head)
{
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//反转链表
struct ListNode* ReverseList(struct ListNode* head)
{
    //只有一个结点/链表为空不用反转
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode*n1= NULL,*n2 = head,*n3 = head->next;
    while(n2)
    {
        // 反转
        n2 ->next = n1;
        //迭代往后走
        n1 = n2;
        n2 = n3;
        //防止n3为空时还往后走，对空指针解引用
        if(n3 != NULL)
        {
            n3 = n3->next;
        }
    }
    return n1;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A == NULL)
        {
            return false;
        }
        //找中间结点
        struct ListNode* mid = MidNode(A);
        //反转中间结点后面的内容
        struct ListNode* rhead = ReverseList(mid);
        //遍历前后两部分链表
        struct ListNode* curA = A;
        struct ListNode* curR = rhead;
        while(curA && curR)
        //while(curR)可以 
        //while(curA)不可以
        {
            if(curA->val != curR->val)
            {
                return false;
            }
            curA = curA->next;
            curR = curR->next;
        }
        return true;
    }
};

为什么判断条件while(curR)可以,while(curA)不可以？

以上面图解的例子

若以curA为循环结束条件，即当curA指向NULL时才跳出循环，像上面这种情况，curR已经指向空了，再进入循环，就是对空指针进行访问了，出错

若以curR为循环结束条件是可以的

若是回文结构：奇数个结点时：curA和curR同时指向NULL结束偶数个结点时：curR比curA先指向NULL结束

若不是回文，二者都不会走到NULL，比较时就返回false了

所以循环条件可以写成：while(curA&& curR) ->含义时：curA和curR都不为空就继续，其中一个为空就跳出循环

也可以写成while(curR)

但是不可以写成while(curA)