文章目录

前言

一、题目引入

二、题解过程

1.迭代方式

2.递归

总结

前言

  最近开始正式学习数据结构。对于链表的系列基本操作，窃以为“反转”，也就是倒置这一块较难，且以此文浅浅记录一下我的理解。废话不多说，上操作！

一、题目引入

  本题要求实现一个函数，实现从尾到头打印一个单链表的功能。例如，如果给出单链表1 2 3 4 5，则应该输出5 4 3 2 1 。注意：每个数据后面一个空格。

 裁判测试程序样例：

#include 
#include 


typedef struct LNode
{
    int data;
    struct LNode *next;
} LinkNode;


void printListFromTail2Head(LinkNode* head);


LinkNode* buildList(int* arr, int n);

int main(void)
{
    int n, i;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    LinkNode* head = buildList(arr, n);
    printListFromTail2Head(head);
    printf("n");

    free(arr);

    return 0;
}

  以上就是完整的题目要求，该题引自pta。 

二、题解过程

1.迭代方式

  首先，我们要清楚的是，反转链表并不是说是把第一个结点的数据移动到最后的结点，它不是数据的移动，而应该是像调整链接，使链表倒置过来。like this:

那么我们可以使用循环来遍历链表，遇到结点我们就调整链接部分，将它的地址字段设置为前一个结点的地址，使它指向前一个结点而不是后一个。如何实现呢？首先，我们将使用一个变量temp，它是一个指向结点的指针。我们先将temp设置为head,也就是让它指向第一个结点。在接下来的循环中只要temp！=NULL，我们就访问到下一个地址。现在在链表中，我们始终知道下一个结点的地址，对于前一个地址，我们就需要设置另外一个变量prev来跟踪前一个结点，最初我们将它设置为NULL。在循环中我们会同时更新这两个变量，用来存储当前结点和前一个结点。接下来遍历链表，如果temp是一个有效的结点，那我们就可以temp->next=prev。现在我们调整了一个链接。为了不丢失原来下一个的地址，在这一步迭代之前，我们又不得不再引入一个临时变量temp1。为了便于理解，我们将之前设置的temp变量改为current，来表示迭代中每个阶段的当前结点。

上代码：

void printListFromTail2Head(LinkNode* head){
    LinkNode *current,*prev,*temp1; 
    current = head; 
    prev =NULL;
while(current!=NULL)
{ 
temp1 =current->next; 
current->next=prev; 
prev=current; current =temp1;}
head = prev; 
    LinkNode* p=head;
    while(p!=NULL){
        	printf("%d ",p->data );
        p=p->next;
    }
}

2.递归

先上代码，如下：

void printListFromTail2Head(LinkNode* head){
    if(head == NULL) return;

    printListFromTail2Head(head->next);
    printf("%d ",head->data);
}

一整个让人很舒服的大动作。首先，我们向函数中传递一个结点。最初，是头节点的地址。如果传递的地址是NULL,则退出。否则我们就进行递归调用并传递结点。

---

总结

  用迭代的方法时，画图会更形象一点，加快理解，虽然但是我没画。第一次发文记录，我可能说的并不是很清楚，希望后续能组织更加准确和详尽的语言来描述~