单链表倒置

题目：将一个单链表倒置，1->2->3->4倒置成4->3->2->1
题目并不难，关键是在面试中思路要清晰。

思路

一定要寻找一个通用场景来完成主代码的测试编写。

结构体定义

面试中简单画了一个图，只尝试了前面两个数的倒置，写成如下：
定义的结构体如下，缺点未使用typedef或者现实好构造函数。

struct mlist
{
    int data;
    struct mlist* next;
};

最好定义如下这种，实现下构造函数，在测试时不需要再给data复制。

struct MyList {
    int data;
    MyList* next;
    MyList(int a) : data(a), next(nullptr) {}
};

错误的主函数

主函数的实现过程有严重的错误，只考虑了第一个和第二个元素的倒置，缺丢失了后面元素的倒置，导致这里存在死循环。

struct mlist* fun(struct mlist* h)
{
    struct mlist* p = h->next;

    while (p != nullptr) {
        h->next = p->next;
        p->next = h;
        h = p;
        p = h->next;
    }
    return h;
}

错误的代码运行示意图

正确的主函数

一般的场景是：链表头h指针指向链表头，当前需要被倒置的节点p指向链表中间任何一个节点（这就出现了测试边界值：p指向头节点后一个节点，p指向中间某个一个节点，p指向最后一个节点）

MyList* fun(MyList* h)
{
    if (h == nullptr) {
        return h;
    }
    MyList* p = h->next;
    MyList* p1;
    MyList* p2;
    MyList* prep = h;

    while (p != nullptr) {
        p1 = p->next;
        p2 = prep;

        prep->next = p->next;
        p->next = h;
        h = p;
        
        prep = p2;
        p = p1;
    }

    return h;
}

void print(MyList* h)
{
    MyList* p = h;
    while (p != nullptr) {
        cout << p->data << endl;
        p = p->next;
    }
    cout << endl;
}

int main()
{
    MyList a(1);
    MyList b(2);
    MyList c(3);
    MyList d(4);

    a.next = &b;
    b.next = &c;
    c.next = &d;

    print(&a);
    MyList* h = fun(&a);
    print(h);

    return 0;
}