题解 | #反转链表#

递归法进行链表反转

用两个指针获取当前节点与后继结点，并逐层递归寻找到后继节点为空时，当前节点为头节点，将传入的returnNode二级指针记录对应头节点地址并返回，逐层将后继节点next指向当前节点，以此完成反转。

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
void reverseOne(struct ListNode* currNode, struct ListNode** returnNode)
{
    struct ListNode* nextNode = currNode->next;

    if(nextNode != NULL)
    {
        reverseOne(nextNode, returnNode);
        nextNode->next = currNode;
        return;
    }

    *returnNode = currNode;
    return;

}
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* returnNode = NULL;

    if(pHead == NULL)
    {
        return NULL;
    }

    reverseOne(pHead, &returnNode);
    pHead->next = NULL;

    return returnNode;

}

利用三指针进行链表反转

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* prevNode;
    struct ListNode* curNode;
    struct ListNode* nextNode;

    if(pHead == NULL)
    {
        return NULL;
    }

    curNode = pHead;
    nextNode = pHead->next;

    curNode->next = NULL;

    while(nextNode != NULL)
    {
        prevNode = curNode;
        curNode = nextNode;
        nextNode = curNode->next;

        curNode->next = prevNode;

    }

    return curNode;

}