【C语言】反转链表

目录

• 迭代法
• 递归法

迭代法

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


/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    //empty or only one node
    if(pHead == NULL || pHead->next == NULL)
        return pHead;
    
    struct ListNode* node_before = NULL;
    struct ListNode* node = pHead; 
    struct ListNode* node_after = pHead->next; 
    
    while(1){
        node->next = node_before;
        if(node_after == NULL)
            break;
        //平移指针
        node_before = node;
        node = node_after;
        node_after = node_after->next;
    }
    pHead = node;
    return pHead;
}

递归法

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



/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    if(pHead == NULL || pHead->next == NULL)
        return pHead;
    
    struct ListNode* newHead = ReverseList(pHead->next);
    
    pHead->next->next =pHead;
    pHead->next = NULL;
    
    return newHead;
}