在这个问题中,我们给出了一个链表。我们的任务是创建一个程序来反转链表。
该程序将反转给定的链表并返回反转后的链表。
链表是一个包含项目的链接序列。每个链接包含到另一个链接的连接。
示例
9 -> 32 -> 65 -> 10 -> 85 -> NULL
登录后复制
反转链表是通过反转链表的链接来创建链表的链表。链表的头节点将成为链表的最后一个节点,而最后一个节点将成为头节点。
示例
从上述链表中形成的反转链表 −
85 -> 10 -> 65 -> 32 -> 9 -> NULL
登录后复制
为了反转给定的链表,我们将使用三个额外的指针来进行处理。这些指针分别是previous、after和current。
我们将初始时将previous和after都设置为NULL,将current设置为链表的头部。
在此之后,我们将迭代直到达到初始链表的NULL。然后执行以下操作:
after = current ->
next current ->
next = previous
previous = current
current = after
登录后复制
现在让我们为反转链表创建一个程序。有两种方法可以创建该程序,一种是迭代方法,另一种是递归方法。
反转链表的程序(尾递归方法)
示例
演示
#include
struct Node {
int data;
struct Node* next;
};
Node* insertNode(int key) {
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
if (!current->next) {
*head = current;
current->next = previous;
return;
}
Node* next = current->next;
current->next = previous;
tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
if (!head)
return;
tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("
");
}
int main(){
Node* head1 = insertNode(9);
head1->next = insertNode(32);
head1->next->next = insertNode(65);
head1->next->next->next = insertNode(10);
head1->next->next->next->next = insertNode(85);
printf("Linked list : t");
printLinkedList(head1);
tailRecReveseLL(&head1);
printf("Reversed linked list : t");
printLinkedList(head1);
return 0;
}
登录后复制
输出
Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9
登录后复制
反转链表的程序(迭代方法)
示例
实时演示
#include
struct Node {
int data;
struct Node* next;
Node(int data){
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList(){
head = NULL;
}
void interReverseLL(){
Node* current = head;
Node *prev = NULL, *after = NULL;
while (current != NULL) {
after = current->next;
current->next = prev;
prev = current;
current = after;
}
head = prev;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp-> data);
temp = temp->next;
}
printf("
");
}
void push(int data){
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList linkedlist;
linkedlist.push(85);
linkedlist.push(10);
linkedlist.push(65);
linkedlist.push(32);
linkedlist.push(9);
printf("Linked List : t");
linkedlist.print();
linkedlist.interReverseLL();
printf("Reverse Linked List : t");
linkedlist.print();
return 0;
}
登录后复制
输出
Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9
登录后复制
以上就是反转链表的C程序的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!