链表的反转有较多的方法,如原地算法,迭代法、头插法、递归法,本文使用递归法和迭代法两种方式进行演示。
一、定义链表
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);
}