题解 | #反转链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        ListNode* L;
        ListNode* p;
        ListNode* q;
        if(head==NULL){
            return NULL;
        }
        L=head;
        p=head->next;
        L->next=NULL;
        while(p!=NULL){
            q=p->next;
            p->next=L;
            L=p;
            p=q;
        }
return L;
        

    }
};

反转链表， 例如:A->B->C->D 反转之后变成 D->C->B->A。我们要借助几个辅助的指针

ListNode* L; ListNode* p; ListNode* q。首先，A->B->C->D 反转后，L=head; A到了尾,L->next=NULL;

在此操作前，为了避免断链，需要先用一个指针指向头节点的下一个 p=head->next; 这样实际上就是需要处理成 A->NULL 和B->C->D。当前p是头节点的下一个，也就是指向B，while循环对其判断是否为空，当头节点的下一个存在时， 用另外一个辅助指针指向p的下一个，q=p->next;这样做的目的是为了对当前p指向的节点进行操作时避免断链（在进行其他操作前，先指向当前节点的下一个节点，避免因在当前指向对象上的操作造成断链）。

当前p仍然指向B,q指向C。我们需要处理成B-> A->NULL和C->D,也就是把一开始的L接到B后面 ，p->next=L;这时候，就会造成原始B->C之间的断链。好在我们有q指向C。此时需要对L p 进行更新，L=p; L指向反转后的链表头，p=q;p指向断链后的部分。

此时就是完成了AB两个的反转，接下来处理C。同样先用辅助指针指向C的下一个q=p->next;。然后可以断链，C的next接上B-> A->NULL ， p->next=L。变成C->B-> A->NULL和D。此时需要对L p 进行更新，L=p; L指向反转后的链表头，p=q;p指向断链后的部分。这部分操作都是while循环中的。此时就剩下D，也就是当前q指向的D，当前p仍然是指向C,while循环还没有结束。

我们对D进行处理，仍然先用辅助指针指向D的下一个。q=p->next; 这时候q是NULL，因为D就是最后一个了，next为null。接下来，把C->B-> A->NULL接到D.next。就是D->C->B-> A->NULL。此时需要对L p 进行更新，L=p; L指向反转后的链表头，p=q;p指向断链后的部分。p指向部分为null，所以不满足下一次while循环条件。

整个过程中需要L都是指向反转后的链表的头A->NULL ，B-> A->NULL，C->B-> A->NULL，D->C->B-> A->NULL，那么最后返回的就是指针L。