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

题目要求

链接：链表的回文结构_牛客题霸_牛客网 (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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

方法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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

---

为什么判断条件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)

---