反转链表

yunshengd / 2023-05-03 / 原文

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为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 };