题解 | #反转链表#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 *
 * @param pHead ListNode类
 * @return ListNode类
 */

//使用头插法反转链表
//头结点也有值，就是相当于不带头结点的链表逆置
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    //该链表为空或只有一个结点时直接返回结果
    if (pHead == NULL || pHead->next == NULL) {
        return pHead;
    }
    struct ListNode* newHead, *p, *q;
    newHead = pHead;
    p = pHead->next;
    pHead->next = NULL; //当前第一个结点即为逆置后的最后一个结点，将其next提前设置为NULL
    while (p) {
        q = p->next;
        p->next = newHead;
        newHead = p;
        p = q;
    }
    return newHead;
}

由于头结点也保存了数据，就相当于不带头结点的链表逆置，采用双指针+头插法逆置。