牛客网反转链表

BM1 反转链表

简单  通过率：40.38%  时间限制：1秒  空间限制：64M

知识点链表

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：  0≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

 

 

示例1

输入：

{1,2,3}

复制返回值：

{3,2,1}

复制

示例2

输入：

{}

复制返回值：

{}

实现算法： 

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * 算法思想： 
 * 将链表中的节点（node）依次插入到头节点之前就能实现逆序。
 */
 
/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
 
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // 参数检查
    if (pHead == NULL) {
        return NULL; 
    }
 
    struct ListNode * p = pHead->next; 
    // 头节点反转后变为尾节点，需要将next域设置为NULL
    pHead->next = NULL; 
    while(p != NULL) {
        /* 在头节点之前插入一个节点 */
        struct ListNode *node = p; 
        p = p->next; 
        node->next = pHead; 
        pHead = node; 
    } 
    return pHead; 
}