题解 | #反转链表#

思索了许久，我想出了不带头结点的做法，依旧是利用头插法，代码如下：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here'
    struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));//p结点头***链表
    struct ListNode* q=(struct ListNode*)malloc(sizeof(struct ListNode));//q记录p的下一个结点
    p=pHead;
    pHead=NULL;
    while(p)
    {
        q=p->next;
        p->next=pHead;
        pHead=p;
        p=q;
    }
    return pHead;
}

该题是将一个不带头结点的链表逆置，由于我不会不带头结点的解法，故构造了一个头结点指向链表表头，代码如下：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here'
    struct ListNode* L=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));//p结点头***链表
    struct ListNode* q=(struct ListNode*)malloc(sizeof(struct ListNode));//q记录p的下一个结点
    L->next=pHead;
    p=L->next;
    L->next=NULL;
    while(p)
    {
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    }
    pHead=L->next;
    return pHead;
}