题目
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
分析
数组+双指针
我们可以先遍历一遍计算出长度，然后再创建数组，再遍历一遍把节点数据放入数组中，然后在数组俩头，俩俩判断。
时间复杂度为O(n)，空间复杂度O(n)；
注：链表的头部不存储数据。所以在计算长度或者输出时，需要从head->next开始。
C
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef struct node LNode; struct node { int data; LNode* next; }; LNode* CreateEndLinkList()//尾插法创建单链表 { LNode* head = NULL; LNode* q = NULL; LNode* p = NULL; int size = 0; head = (LNode*)malloc(sizeof(LNode));//申请头节点空间 q = head; if (NULL == head) { perror("申请空间失败"); exit(EXIT_FAILURE); } head->data = 0; head->next = NULL; printf("请输入需要添加的节点个数:"); scanf("%d", &size); printf("请依次输入节点的值(用空格隔开):\n"); while (size > 0) { p = (LNode*)malloc(sizeof(LNode));//申请子节点空间 scanf("%d", &p->data); p->next = NULL;//尾插入 q->next = p; q = p; size--; } return head; } int LengthLinkList(LNode* head)//单链表长度 { int len = 0; LNode* p = head->next; while (NULL != p) { len++; p = p->next; } return len; } void DelAllLinkList(LNode* head)//释放整个表 递归 { if (head != NULL) { DelAllLinkList(head->next); } free(head); } void PrintLinkList(LNode* head)//输出链表数据 { LNode* p = head->next; while (NULL != p) { printf("%d ", p->data); p = p->next; } } //判断链表是否为回文链表 //是回文返回true 不是回文返回false bool isPalindrome(LNode* head) { int mark = true; //记录是否回文 int len = LengthLinkList(head); int* n = (int*)malloc(sizeof(int) * len); int i = 0; LNode* p = head->next; while (NULL != p)//遍历链表 存入数组 { n[i] = p->data; p = p->next; i++; } int start = 0; //前指针 int end = len - 1; //后指针 while (start < end) { if (n[start] != n[end])//一次不等直接跳出。 { mark = false; break; } start++; end--; } return mark; } int main() { LNode* head = CreateEndLinkList(); bool ret = isPalindrome(head); if (ret == true) { printf("该链表是回文链表！\n"); } else { printf("该链表不是回文链表！\n"); } DelAllLinkList(head); return 0; }
快慢指针+反转链表
让快指针一次走俩步，慢指针一次走一步。当快指针停下的时候，慢指针走到中间或者中间靠右。主要是取决于节点数量为偶数和奇数。如下图
上图节点数为偶数
下图节点数为奇数
我们就可以将找中间值这段代码实现出来，如下
LNode* fast = head;//快指针 LNode* slow = head;//慢指针 /* * *如果是奇数列 找最中间的 * *如果是偶数列 找左边的中间值 */ while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; }
接下来我们就要开始反转链表了。
我们发现无论是哪种情况，需要反转的链表都是从下一个节点开始。当前节点 = slow->next;
这里我们就拿偶数举例，这里我们需要三个指针前指针、当前节点指针和后指针，反转如下图。核心四步骤。(奇数也一样，读者可以自行研究)
反转后的成品图为：
反转代码实现如下：
LNode* front = NULL; //前指针 LNode* present = slow->next;//需要反转的节点 LNode* later = present; //后指针 while (present != NULL) //反转后半部分 { later = later->next; present->next = front; front = present; present = later; }
然后就是判断是否为回文链表，还是双指针思想，刚好从反转后的成品图中看出最后front
前指针当好指向的就是尾节点。终止条件就是后指针向前走会走到NULL。实现如下
front = head; //前指针 later = front; //后指针 /*判断回文*/ while (later != NULL)//后指针走到空为止 { if (front->data != later->data) { mark = false; } front = front->next; later = later->next; }
这时候我们的目的已经达到了。但是我们却把链表结构该修改了，所以我们还需要把链表复原。复原的思想和反转思想一样，但是前指针后后指针指向的刚好相反，在反转的时候，是后指针去探路。在复原的时候变成了前指针去探路。实现如下
/*复原链表*/ later = NULL; //后指针 present = fast; //需要反转的节点 最右边 front = present;//前指针 while (front != NULL) { front = front->next; present->next = later; later = present; present = front; }
然后将代码整合，
C
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef struct node LNode; struct node { int data; LNode* next; }; LNode* CreateEndLinkList()//尾插法创建单链表 { LNode* head = NULL; LNode* q = NULL; LNode* p = NULL; int size = 0; head = (LNode*)malloc(sizeof(LNode));//申请头节点空间 q = head; if (NULL == head) { perror("申请空间失败"); exit(EXIT_FAILURE); } head->data = 0; head->next = NULL; printf("请输入需要添加的节点个数:"); scanf("%d", &size); printf("请依次输入节点的值(用空格隔开):\n"); while (size > 0) { p = (LNode*)malloc(sizeof(LNode));//申请子节点空间 scanf("%d", &p->data); p->next = NULL;//尾插入 q->next = p; q = p; size--; } return head; } int LengthLinkList(LNode* head)//单链表长度 { int len = 0; LNode* p = head->next; while (NULL != p) { len++; p = p->next; } return len; } void DelAllLinkList(LNode* head)//释放整个表 递归 { if (head != NULL) { DelAllLinkList(head->next); } free(head); } void PrintLinkList(LNode* head)//输出链表数据 { LNode* p = head->next; while (NULL != p) { printf("%d ", p->data); p = p->next; } } //判断链表是否为回文链表 //是回文返回true 不是回文返回false bool isPalindrome(LNode* head) { bool mark = true; LNode* fast = head;//快指针 LNode* slow = head;//慢指针 /* * *如果是奇数列 找最中间的 * *如果是偶数列 找左边的中间值 */ while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; } /* * *如果快指针的下一个不为空。就再走一步 */ if (fast->next != NULL) { fast = fast->next; } LNode* front = NULL; //前指针 LNode* present = slow->next;//需要反转的节点 LNode* later = present; //后指针 while (present != NULL) //反转后半部分 { later = later->next; present->next = front; front = present; present = later; } front = head; //前指针 later = front; //后指针 /*判断回文*/ while (later != NULL)//后指针走到空为止 { if (front->data != later->data) { mark = false; } front = front->next; later = later->next; } /*复原链表*/ later = NULL; //后指针 present = fast; //需要反转的节点 最右边 front = present;//前指针 while (front != NULL) { front = front->next; present->next = later; later = present; present = front; } return mark; } int main() { LNode* head = CreateEndLinkList(); bool ret = isPalindrome(head); if (ret == true) { printf("该链表是回文链表！\n"); } else { printf("该链表不是回文链表！\n"); } DelAllLinkList(head); return 0; }
该方法虽然过程繁琐，但是空间复杂度大大降低。时间复杂度为O(n),空间复杂度O(1);
递归+双指针
我们通过递归的思想让一个指针走到链表尾端，然后依次对比。实现思想较难，请读者自行画图理解。
核心代码单独列出来
LNode* front = NULL; //前指针 //递归判断回文 //有一次false就是false。只有都是true才是true bool recursion(LNode* head) { if (head != NULL) { if (recursion(head->next) == false)//上一次判断是false 就直接返回 { return false; } if (head->data != front->data) //当前俩节点值不相等 { return false; } front = front->next;//前指针往后走 } return true; } //判断链表是否为回文链表 //是回文返回true 不是回文返回false bool isPalindrome(LNode* head) { front = head; return recursion(head); }
总代码
C
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef struct node LNode; struct node { int data; LNode* next; }; LNode* CreateEndLinkList()//尾插法创建单链表 { LNode* head = NULL; LNode* q = NULL; LNode* p = NULL; int size = 0; head = (LNode*)malloc(sizeof(LNode));//申请头节点空间 q = head; if (NULL == head) { perror("申请空间失败"); exit(EXIT_FAILURE); } head->data = 0; head->next = NULL; printf("请输入需要添加的节点个数:"); scanf("%d", &size); printf("请依次输入节点的值(用空格隔开):\n"); while (size > 0) { p = (LNode*)malloc(sizeof(LNode));//申请子节点空间 scanf("%d", &p->data); p->next = NULL;//尾插入 q->next = p; q = p; size--; } return head; } int LengthLinkList(LNode* head)//单链表长度 { int len = 0; LNode* p = head->next; while (NULL != p) { len++; p = p->next; } return len; } void DelAllLinkList(LNode* head)//释放整个表 递归 { if (head != NULL) { DelAllLinkList(head->next); } free(head); } void PrintLinkList(LNode* head)//输出链表数据 { LNode* p = head->next; while (NULL != p) { printf("%d ", p->data); p = p->next; } } LNode* front = NULL; //前指针 //递归判断回文 //有一次false就是false。只有都是true才是true bool recursion(LNode* head) { if (head != front) { if (recursion(head->next) == false)//上一次判断是false 就直接返回 { return false; } if (head->data != front->data) //当前俩节点值不相等 { return false; } front = front->next;//前指针往后走 } return true; } //判断链表是否为回文链表 //是回文返回true 不是回文返回false bool isPalindrome(LNode* head) { front = head; return recursion(head); } int main() { LNode* head = CreateEndLinkList(); bool ret = isPalindrome(head); if (ret == true) { printf("该链表是回文链表！\n"); } else { printf("该链表不是回文链表！\n"); } DelAllLinkList(head); return 0; }
本章完！
