C++程序 检查单链表是否是回文
给定一个由字符组成的单链表,编写一个函数,如果给定的列表是回文的,则返回true,否则返回false。
方法1(使用堆栈):
- 一个简单的解决方法是使用一个节点列表的堆栈。这主要包括三个步骤。
- 从头到尾遍历给定的列表,并将每个访问的节点推入堆栈中。
- 再次遍历列表。对于每个访问的节点,从堆栈弹出一个节点并将弹出节点的数据与当前访问的节点进行比较。
- 如果所有节点都匹配,则返回true,否则返回false。
下面的图像是上述方法的干运行:
下面是上述方法的实现:
// C++程序来实现
// 上面的方法
#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node(int d)
{
data = d;
}
Node *ptr;
};
// 检查链表是否是回文或不
bool isPalin(Node* head)
{
// 暂时指针
Node* slow= head;
// 声明一个堆栈
stack <int> s;
// 将列表的所有元素推送到堆栈中
while(slow != NULL)
{
s.push(slow->data);
// 前进
slow = slow->ptr;
}
// 再次迭代列表并
// 通过从堆栈中弹出来检查
while(head != NULL )
{
// 获取最顶端的元素
int i=s.top();
// 弹出元素
s.pop();
// 检查数据是否不同
// 与弹出元素
if(head -> data != i)
{
return false;
}
// 前进
head=head->ptr;
}
return true;
}
// 驱动程序
int main()
{
// 链表的加法
Node one = Node(1);
Node two = Node(2);
Node three = Node(3);
Node four = Node(2);
Node five = Node(1);
// 初始化每个当前指针的下一个指针
five.ptr = NULL;
one.ptr = &two
two.ptr = &three
three.ptr = &four
four.ptr = &five
Node* temp = &one
// 调用函数检查
// 你是否回文
int result = isPalin(&one);
if(result == 1)
cout << "isPalindrome is true";
else
cout << "isPalindrome is true";
return 0;
}
// 此代码由Striver贡献```
输出:
isPalindrome: true
时间复杂性: O(n),其中n表示给定链表的长度。
辅助空间: O(n),用于使用堆栈,其中n表示给定链表的长度。
方法2(通过翻转列表):
此方法需要O(n)的时间和O(1)的附加空间。
1) 获取链表的中间。
2) 翻转链表的后半部分。
3) 检查第一半和第二半是否相同。
4) 通过再次翻转第二半并将其附加回第一半来构造原始链表。
要将列表分成两半,请使用本帖子的方法2。
当节点的数量为偶数时,第一半和第二半恰好包含一半的节点。这种方法中的挑战是处理节点数量为奇数的情况。我们不希望将中间节点作为列表的一部分,因为我们要对它们进行比较来判断它们是否相等。对于奇数情况,我们使用单独的变量“midnode”。
// C++ program to check if a linked list
// is palindrome
#include <bits/stdc++.h>
using namespace std;
// Link list node
struct Node
{
char data;
struct Node* next;
};
void reverse(struct Node**);
bool compareLists(struct Node*,
struct Node*);
// Function to check if given linked list
// is palindrome or not
bool isPalindrome(struct Node* head)
{
struct Node *slow_ptr = head,
*fast_ptr = head;
struct Node *second_half,
*prev_of_slow_ptr = head;
// To handle odd size list
struct Node* midnode = NULL;
// initialize result
bool res = true;
if (head != NULL &&
head->next != NULL)
{
// Get the middle of the list.
// Move slow_ptr by 1 and fast_ptrr
// by 2, slow_ptr will have the middle
// node
while (fast_ptr != NULL &&
fast_ptr->next != NULL)
{
fast_ptr = fast_ptr->next->next;
// We need previous of the slow_ptr
// for linked lists with odd elements
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr->next;
}
// fast_ptr would become NULL when there
// are even elements in list. And not NULL
// for odd elements. We need to skip the
// middle node for odd case and store it
// somewhere so that we can restore the
// original list
if (fast_ptr != NULL)
{
midnode = slow_ptr;
slow_ptr = slow_ptr->next;
}
// Now reverse the second half and
// compare it with first half
second_half = slow_ptr;
// NULL terminate first half
prev_of_slow_ptr->next = NULL;
// Reverse the second half
reverse(&second_half);
// compare
res = compareLists(head, second_half);
// Construct the original list back
// Reverse the second half again
reverse(&second_half);
// If there was a mid node (odd size case)
// which was not part of either first half
// or second half.
if (midnode != NULL)
{
prev_of_slow_ptr->next = midnode;
midnode->next = second_half;
}
else
prev_of_slow_ptr->next = second_half;
}
return res;
}
// Function to reverse the linked list
// Note that this function may change
// the head
void reverse(struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
// Function to check if two input
// lists have same data
bool compareLists(struct Node* head1,
struct Node* head2)
{
struct Node* temp1 = head1;
struct Node* temp2 = head2;
while (temp1 && temp2)
{
if (temp1->data == temp2->data)
{
temp1 = temp1->next;
temp2 = temp2->next;
}
else
return 0;
}
// Both are empty return 1
if (temp1 == NULL && temp2 == NULL)
return 1;
// Will reach here when one is NULL
// and other is not
return 0;
}
// Push a node to linked list. Note
// that this function changes the head
void push(struct Node** head_ref,
char new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list of the new node
new_node->next = (*head_ref);
// Move the head to point to the new node
(*head_ref) = new_node;
}
// A utility function to print a
// given linked list
void printList(struct Node* ptr)
{
while (ptr != NULL)
{
cout << ptr->data << "->";
ptr = ptr->next;
}
cout << "NULL" << "";
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = NULL;
char str[] = "abacaba";
int i;
for(i = 0; str[i] != ''; i++)
{
push(&head, str[i]);
printList(head);
isPalindrome(head) ? cout << "Is Palindrome" <<
"" : cout << "Not Palindrome" << "";
}
return 0;
}
输出:
a->NULL
Is Palindrome
b->a->NULL
Not Palindrome
a->b->a->NULL
Is Palindrome
c->a->b->a->NULL
Not Palindrome
a->c->a->b->a->NULL
Not Palindrome
b->a->c->a->b->a->NULL
Not Palindrome
a->b->a->c->a->b->a->NULL
Is Palindrome
时间复杂度: O(n)
辅助空间: O(1)
方法3(使用递归):
使用两个指针left和right。使用递归移动right和left,每次递归调用时检查以下内容。
1)子列表是回文字符串。
2)当前left和right的值匹配。
如果上述两个条件都为true,则返回true。
这个思想是使用函数调用堆栈作为容器。递归遍历到列表末尾。当我们从最后一个NULL返回时,我们将在最后一个节点上。与列表的第一个节点进行比较。
为了访问列表的第一个节点,我们需要在递归函数的最后一个调用中使列表头可用。因此,我们也将head传递给递归函数。如果它们都匹配,则需要比较(2,n-2)节点。再次递归回到(n-2)号节点时,我们需要从头指向第2个节点。我们在上一个调用中推进head指针,以引用列表中的下一个节点。
然而,识别双指针的诀窍是。传递单个指针与传递值一样好,我们将一遍又一遍地传递相同的指针。我们需要传递head指针的地址以反映父递归调用中的更改。
//递归程序以检查给定的链表是否为回文
# include <bits/stdc++.h>
using namespace std;
//链接列表节点
struct node
{
char data;
struct node* next;
};
//此函数的初始参数是&head和head
bool isPalindromeUtil(struct node** left,
struct node* right)
{
//当right变为NULL时停止递归
if (right == NULL)
return true;
/*如果子列表不是回文,则不需要
需要检查当前左和右侧,
返回false*/
bool isp = isPalindromeUtil(left,
right->next);
if (isp == false)
return false;
//检查当前左和右的值
bool isp1 = (right->data == (*left)->data);
//将左移动至下一个节点
*left = (*left)->next;
return isp1;
}
//一个包装器isPalindromeUtil()
bool isPalindrome(struct node* head)
{
isPalindromeUtil(&head, head);
}
/*将节点推入链接的列表。请注意
此函数更改标头*/
void push(struct node** head_ref,
char new_data)
{
//分配节点
struct node* new_node =
(struct node*)malloc(sizeof(struct node));
//放入数据
new_node->data = new_data;
//链接新节点的旧列表
new_node->next = (*head_ref);
//将头移动到新节点的位置
(*head_ref) = new_node;
}
//打印指定链接列表的实用程序函数
void printList(struct node* ptr)
{
while (ptr != NULL)
{
cout << ptr->data << "->";
ptr = ptr->next;
}
cout << "NULL" ;
}
//主代码
int main()
{
//从空列表开始
struct node* head = NULL;
char str[] = "abacaba";
int i;
for (i = 0; str[i] != ''; i++)
{
push(&head, str[i]);
printList(head);
isPalindrome(head) ? cout <<
"Is Palindrome" : cout << "Not Palindrome";
}
return 0;
}
//此代码由shivanisinghss2110提供```
输出:
a->NULL
Not Palindrome
b->a->NULL
Not Palindrome
a->b->a->NULL
Is Palindrome
c->a->b->a->NULL
Not Palindrome
a->c->a->b->a->NULL
Not Palindrome
b->a->c->a->b->a->NULL
Not Palindrome
a->b->a->c->a->b->a->NULL
Is Palindrome
时间复杂度: O(n)
辅助空间: O(n),如果考虑函数调用堆栈大小,则为O(1)。