首页 > 代码库 > 将单链表翻转的两种方法
将单链表翻转的两种方法
将一个单链表翻转的描述很简单,例如:
输入: NODE1->NODE2->NODE3->NODE4->NODE5->NULL
输出: NODE5->NODE4->NODE3->NODE2->NODE1->NULL
那么,定义单链表如下: (为简单起见,将data字段定义为int, 当然实际应用中data很可能是一个复杂的结构体)
typedef struct list_s { int data; struct list_s *next; } list_t;
如何将单链表翻转,有如下两种方法。
- 使用N个辅助存储空间aux[],N为单链表中所有结点的个数。将所有结点的地址反向存入aux[]中,然后根据aux[]重新生成一个单链表。
- 只使用2个辅助存储空间,从头到尾遍历单链表并翻转。
其中,方法1使用了较多的辅助存储空间,但实现起来很简单,有点类似使用栈的意思。
方法1的代码实现如下:
o foo1.c
1 static int get_length(list_t *head) 2 { 3 int len = 0; 4 for (list_t *p = head; p != NULL; p = p->next) 5 len++; 6 return len; 7 } 8 9 void reverse_single_linked_list(list_t **head) 10 { 11 if (*head == NULL) 12 return; 13 14 int len = get_length(*head); 15 if (len < 2) 16 return; 17 18 list_t **aux = (list_t **)malloc(sizeof (list_t *) * len); 19 if (aux == NULL) /* error */ 20 return; 21 22 /* save addr of per node to aux[] */ 23 int index = 0; 24 for (list_t *p = *head; p != NULL; p = p->next) { 25 aux[len-1-index] = p; 26 index++; 27 } 28 29 /* rebuild the linked list by walking aux[] */ 30 *head = (list_t *)aux[0]; 31 for (int i = 0; i < len-1; i++) 32 ((list_t *)aux[i])->next = aux[i+1]; 33 ((list_t *)aux[len-1])->next = NULL; 34 35 free(aux); 36 }
方法2的代码实现如下:
o foo2.c
void reverse_single_linked_list(list_t **head) { list_t *newhead = NULL; list_t *this = *head; list_t *prev = NULL; while (this != NULL) { /* * If this->next is NULL, this is the tail node, which should * be the new head */ if (this->next == NULL) newhead = this; /* * ListIn: prevNode -> thisNode -> nextNode * ListOut: prevNode <- thisNode <- nextNode * 1. thisNode->next = prevNode; * 2. prevNode = thisNode; * 3. thisNode = thisNode->next; */ list_t *t = this->next; this->next = prev; prev = this; this = t; } *head = newhead; }
用meld diff foo1.c foo2.c截图如下:
完整的代码点这里
最后,对单链表翻转函数做单元测试需要考虑三种情况:
- 输入的单链表头结点指针为NULL
- 输入的单链表只有一个结点
- 输入的单链表包含多个结点
将单链表翻转的两种方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。