题目描述
输入一个链表,反转链表后,输出新链表的表头。
题解
一个很简单的办法是将所有指针节点存入一个vector中,然后再重新链接,这样的时间复杂度是2n,空间复杂度是n。
一个更好的办法是遍历链表,直接反转。代码如下
/*
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 *NextPtr = pHead->next, *tmpHeadPtr = pHead;
while(pHead){
if(NextPtr == NULL){
tmpHeadPtr->next = NULL;
return pHead;
}
ListNode* tmp = NextPtr->next;
NextPtr->next = pHead;
pHead = NextPtr;
NextPtr = tmp;
}
}
};
如果想在本地测试一下,下面给出了本地测试可用的代码:
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
ListNode* ReverseList(ListNode* pHead) {
if(!pHead) return NULL;
ListNode *NextPtr = pHead->next, *tmpHeadPtr = pHead;
while(pHead){
if(NextPtr == NULL){
tmpHeadPtr->next = NULL;
return pHead;
}
ListNode* tmp = NextPtr->next;
NextPtr->next = pHead;
pHead = NextPtr;
NextPtr = tmp;
}
}
int main(){
ListNode *head = new ListNode(0), *ptr = head;
int N;
cout << "输入多少数" << endl;
cin >> N;
cout << endl << "读取链表:" << endl;
for(int i = 0; i < N; i++){
int num;
cin >> num;
ptr->next= new ListNode(num);
ptr = ptr->next;
}
ListNode* p = head;
cout << "反转前" << endl;
while(p){
cout << p->val << ' ';
p = p->next;
}
cout << endl << "开始反转" << endl;
p = ReverseList(head);
cout << "反转后" << endl;
while(p){
cout << p->val << ' ';
p = p->next;
}
return 0;
}