反转链表

标签：ListNode 反转 next 链表 pHead 节点

• 描述

给定一个单链表的头结点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

输入：{} 返回值：{} 说明：空链表则输出空    

• 解法1

算法思想：采用链表的头插法来实现链表的逆置  

• 解法2

算法思想：使用四个指针来进行链表的逆置，具体实现如代码注释。    

• 代码 

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 #include <cstdlib>
10 class Solution {
11 public:
12     ListNode* ReverseList(ListNode* pHead) {
13                 //解法一
14         //添加头结点
15         ListNode* p=(ListNode*)malloc(sizeof(ListNode));
16         p->next=nullptr;
17         //头插法
18         ListNode *q=pHead;
19         ListNode *r=q->next;
20         while(q){
21             r=q->next;//暂存q的下一节点
22             q->next=p->next;
23             p->next=q;
24             q=r;
25         }
26         return p->next;
27         //解法二
28         // //特殊情况判断
29         // if(pHead==nullptr) return pHead;
30         // //如例题，p,q记录节点1，2位置，r,s记录节点2，3位置
31         // ListNode *p=pHead;
32         // ListNode *q=p->next;
33         // ListNode *r=q;
34         // ListNode *s=r->next;
35         // pHead->next=nullptr;//头结点的next置空
36         // while(q){
37         //     //为节点2，3的反转做准备
38         //     r=q;
39         //     s=r->next;
40         //     //节点1，2反转
41         //     q->next=p;
42         //     //p,q又成为节点2，3的位置
43         //     p=r;
44         //     q=s;
45         // }
46         // return p;//最终p指向最后一个节点，q指向空
47     }
48 };

 

 

   

标签：ListNode,反转,next,链表,pHead,节点
From： https://www.cnblogs.com/yueshengd/p/17367597.html