力扣 - 234、回文链表-阿里云开发者社区

题目

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

示例 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;
}

本章完！

力扣 - 234、回文链表

题目

分析

热门文章

最新文章

相关电子书