本文共 1186 字，大约阅读时间需要 3 分钟。

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路1

使用额外空间，然后采用头插法将遍历到的结点插入到新建立链表的头部，将原链表的尾结点作为新链表的头结点即可，这种方法消耗的存储空间较大，新建了一个和原来链表一样大小的链表，不推荐。

代码实现

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};*/class Solution {
   public:    ListNode* ReverseList(ListNode* pHead) {
           ListNode *p,*head;        if(!pHead)return NULL;        p=pHead;        ListNode *ptr;        head=NULL;        while(p){
               ptr=new ListNode(p->val);            ptr->next=head,head=ptr,p=p->next;        }        p=head;        return head;    }};

运行时间：2ms占用内存：500k

解题思路2

其实我们只需要将原链表结点的next指向原链表的上一结点，没有就为NULL，为此，我们需要3个指针：

• 一个用来存储当前结点的下一结点（如果没有下一结点，当前结点则作为所求的头结点）
• 一个用来存储链表的上一结点
• 一个用来存储链表的当前结点，并将当前结的next指向链表的上一结点

需要注意的是，在修改当前结点的next时，应保存当前结点的下一结点

代码实现

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};*/class Solution {
   public:    ListNode* ReverseList(ListNode* pHead) {
           if(!pHead)return NULL;        ListNode *p=pHead,*pn,*pre=NULL,*reHead;        while(p){
               pn=p->next;            if(!pn)reHead=p;            p->next=pre,pre=p,p=pn;        }        return reHead;    }};

运行时间：2ms占用内存：472k

转载地址：https://blog.csdn.net/Jeaten/article/details/108356438 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！