单链表的逆序

🧪：创建一个单链表，实现单链表的逆序，并输出。例:输入 1->2->3->4, 输出 4->3->2->1。

requirement

要求结构上的倒序，而不是单纯输出。
递归实现。

---

思路

首先实现链表的数据结构，再利用递归改变链表结构。关键在于递归:
1 -> 2 -> 3 -> 4 -> 5
1 <- reverse( 1->next )
1 <- 2 <- reverse( 2->next )
...
1 <- 2 <- 3 <- 4 <- reverse( 4->next )
1 <- 2 <- 3 <- 4 <- 5 //done!

Note

递归函数：将节点指向的链表逆序后指向该节点，再将该节点改为尾节点。
递归出口：只有一个节点，则返回该节点。

---

实现

Step1: 实现链表数据结构

C

typedef struct node{
    int value;
    struct node *next;
}LinkNode;

Step2: 创建链表
以 -1 为输入结束的标志。

C

LinkNode* Create_link(){
    LinkNode *head, *temp;
    int a;
    head = (LinkNode*)malloc(sizeof(LinkNode));
    ...
    while(a != -1){
        scanf("%d",&a);
        temp -> next = (LinkNode*)malloc(sizeof(LinkNode));
        ...
        temp = temp -> next;
        temp -> value = a;
        temp -> next = NULL;
    }
    return head;
}

Step3: 实现链表输出功能

C

void Print_link(LinkNode *head){
    LinkNode *p;
    p = head;
    while(p != NULL && p -> next != NULL){
        printf("%d -> ", p -> value);
        p = p -> next;
    }
    printf("%d\n", p -> value);
}

Step4: 链表逆序。

分为两个函数来实现。一个是reverse函数，利用递归将链表指针逆转。另一个是Reverse_link函数，负责获取逆转后的头指针。reverse函数被嵌套在Reverse_link函数中。
这样做的原因主要是利用递归逆转链表指针的返回值是末尾元素。无法直接获取头指针。

C

LinkNode* reverse(LinkNode* head){
    LinkNode *p;
    p = head;
    if(p -> next == NULL){
        return p;   //只有一个节点，直接返回
    }else{
        p = head;
        reverse(p -> next) -> next = p;
        p -> next = NULL;
        return p;
    }
}

C

LinkNode* Reverse_link(LinkNode *head){
    LinkNode *p;
    p = head;
    while(p -> next != NULL){
        p = p->next;
    }
    reverse(head);
    return p;
}

Step5: main函数调用。

C

head = Create_link();
newhead = Reverse_link(head);
Print_link(newhead);