剑指offer——JZ24 反转链表 解题思路与具体代码

一、题目描述与要求

反转链表_牛客题霸_牛客网 (nowcoder.com)

题目描述

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

数据范围： 0≤n≤1000

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

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

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

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

示例

示例1：

输入：{1,2,3}

返回值：{3,2,1}

示例2：

输入：{}

返回值：{}

说明：空链表则输出空

---

二、解题思路

【利用辅助指针实现反转】

首先判断是否为空链表，是的话直接返回空，否则提交可能会导致出现“段错误”。然后就是利用两个指针，指针p是用来遍历整个链表并且用来为q赋值；指针q则是依次将每个结点插入到头结点前面。，插入成功之后移动头结点即可。

---

三、具体代码

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