当前位置：首页 > news >正文

链表反转算法

news 来源：原创 2024/9/20 4:48:04

链表的反转有较多的方法，如原地算法，迭代法、头插法、递归法，本文使用递归法和迭代法两种方式进行演示。

一、定义链表

typedef  struct   SinglyLinkNode
{/**后继节点 */struct  SinglyLinkNode* next;/** 节点数据域 */int  data;
} LinkNode;/**** 添加链表元素
*/
void  insert_link_node(LinkNode**  link,int data);/*** 查询链表
*/
void  show_link_list(LinkNode* head);/***递归法 链表反转
*/
LinkNode*  recursion_reversal(LinkNode*  head);/*** 迭代法 链表反转
*/
LinkNode*  iteration_reversal(LinkNode*  head);

二、链表操作

/**** 添加链表元素*/
void insert_link_node(LinkNode** link, int data)
{LinkNode* head=  *link;if (head == NULL){head = malloc(sizeof(LinkNode*));head->data = data;head->next = NULL;(*link) = head;return;}LinkNode* newNode = malloc(sizeof(LinkNode*));newNode->next = NULL;newNode->data = data;while (head!=NULL && head->next!=NULL ){head = head->next;}head->next = newNode;
}/*** 查询链表*/
void show_link_list(LinkNode *head)
{if (head == NULL){return;}printf("\n----\t");LinkNode *next = head;while (next != NULL){printf("%d\t", next->data);next = next->next;}printf("\n------------------------------------\n");
}

三、递归法

LinkNode* recursion_reversal(LinkNode* head)
{if ( head ==NULL || head->next == NULL){return head;}LinkNode* newNode = recursion_reversal(head->next);head->next->next = head;head->next = NULL;return newNode;
}

int main()
{int  arr[] = { 88, 77, 66, 55 , 44, 33 , 22 ,11};LinkNode* head = NULL;int i = 0;for( i ; i < sizeof(arr)/sizeof(int) ; i++ ){insert_link_node(&head,arr[i]);}show_link_list(head);head = recursion_reversal(head);show_link_list(head);while (1) {}exit(0);
}

四、迭代法

/*** 迭代法反转链表
*/
LinkNode*  iteration_reversal(LinkNode*  head)
{if(head==NULL ||  head->next==NULL){return head;}/// 存储当前节点LinkNode* cur = head;/// 存储临时存储前继节点LinkNode* pre = NULL;/// 临时存储当前后继节点LinkNode* next = NULL;while (cur->next!=NULL){next =  cur->next;cur->next = cur->next->next;if(pre == NULL){pre = next;pre->next = cur;head =  pre;}else{LinkNode* tmp =  head;next->next =  tmp;head =  next;}}return head;
}

int main()
{int  arr[] = { 88, 77, 66, 55 , 44, 33 , 22 ,11};LinkNode* head = NULL;int i = 0;for( i ; i < sizeof(arr)/sizeof(int) ; i++ ){insert_link_node(&head,arr[i]);}show_link_list(head);head = iteration_reversal(head);show_link_list(head);while (1) {}///getchar()exit(0);
}