6-1单链表逆转

题目描述

将给定的单链表进行反转

题目地址为:https://pintia.cn/problem-sets/15/problems/724

解法一

解法描述

新建一个空链表，采用头插法就可以将链表反转

这里需要注意的是，新建链表有个头结点，但是需要反转的链表没有头结点

所以最后需要返回的应该是新建链表的下一个结点

List结构定义

typedef struct Node *PtrToNode;

struct Node {

    ElementType Data; /* 存储结点数据 */

    PtrToNode   Next; /* 指向下一个结点的指针 */

};

typedef PtrToNode List; /* 定义单链表类型 */

具体代码

List Reverse( List L ) {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->Next = NULL;
    struct Node* current = L;
    while (current != NULL) {
        struct Node* temp = current->Next;
        current->Next = head->Next;
        head->Next = current;
        current = temp;
    }
    return head->Next;
}

思考

这样写法就非常奇怪，而且在循环中又会引入其他的变量。是否可以不要这个头结点？转而使用判断语句。

因为只需要处理头结点的问题，也就是只需要判断一次就可以完成。

一定要注意循环中链表的移动和位置变换的关系（在之前的代码中current是位于head之后，但是这里就是在head之前，就需要把head赋值为current）

List Reverse( List L ) {
    struct Node* head = NULL;
    struct Node* current = L;
    while (current != NULL) {
        struct Node* temp = current->Next;
        if (!head) {
            head = current;
            head->Next = NULL;
            current = temp;
            continue;
        }
        current->Next = head;
        head = current;
        current = temp;
    }
    return head;
}

解法二

解法描述

所谓反转链表无非是两两结点之间箭头的变换

对比前后的图像就能够很轻易地得出解决方案

具体代码

List Reverse( List L ) {
    struct Node* prev = NULL;
    struct Node* current = L;
    while (current != NULL) {
        struct Node* temp = current->Next;
        current->Next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}