其实这个才是逆序输出链表的正确操作,记得前面写的时候有四种办法,但除了递归比较简洁而且时间复杂度和空间复杂度都满足外,其他的方法都太丑陋了...
Code:
- /* 反转链表的函数 */
- struct reverseList * reverseLinkList(struct reverseList * node)
- {
- struct reverseList * prev, * rear;
-
- rear = node -> next;
- while(rear -> next != NULL) //整体并未向后移动
- {
- prev = rear -> next; //先用一个容器指针来复制一份该指针
- rear -> next = prev -> next; //把被复制的指针后面的一位赋给被复制的指针,意味着告诉被复制的指针的前一个指针,它的下一个是被复制指针的后一个。
- prev -> next = node -> next; //把第一个指针赋给被复制指针的后一个,意味着告诉被复制的指针,它的下一个为第一个
- node -> next = prev; //把复制的指针赋给第一个,意味着告诉头,它的下一个为复制指针
- }
-
- return node;
- }
我推荐可以看看我参考别人的图文解释的文章:点击(ง •_•)ง
完整的代码测试:
- /*
- * 反转单链表 - 非递归实现
- */
-
- #include<stdio.h>
- #include<stdlib.h>
-
- struct reverseList {
- struct reverseList * next;
- int val;
- };
-
- struct reverseList * CreateList(void)
- {
- struct reverseList * head, * s, * current;
- int i;
-
- head = (struct reverseList *)malloc(sizeof(struct reverseList));
- s = head;
- for(i = 0; i < 10; i++)
- {
- current = (struct reverseList *)malloc(sizeof(struct reverseList));
- current -> val = i + 1;
- s -> next = current;
- s = s -> next;
- }
- s -> next = NULL;
-
- return head;
- }
-
- struct reverseList * reverse_Link_List(struct reverseList * node)
- {
- struct reverseList * prev, * rear;
-
- rear = node -> next;
- while(rear -> next != NULL)
- {
- prev = rear -> next;
- rear -> next = prev -> next;
- prev -> next = node -> next;
- node -> next = prev;
- }
-
- return node;
- }
-
- int main(void)
- {
- struct reverseList * head, * p;
-
- head = CreateList();
-
- p = head -> next;
- while(p)
- {
- printf("%d ", p -> val);
- p = p -> next;
- }
- printf("\n");
-
- p = reverse_Link_List(head) -> next;
-
- while(p)
- {
- printf("%d ", p -> val);
- p = p -> next;
- }
- printf("\n");
-
- p = head;
- while(p)
- {
- head = p;
- p = p -> next;
- free(head);
- }
- p = NULL;
-
- return 0;
- }