本文为剑指 offer 系列第十七篇。
主要知识点为链表，还是在链表遍历的基础上做文章，比较简单。
输入一个链表，反转链表后，输出新链表的表头。
解题思路
新建一个结点head表示头结点。
当遍历原来的链表到结点A的时候，创建一个新的节点A’，值等于A结点的值，A’指向原来的head结点，而head结点指向A结点。
如此这般，将原来的链表遍历完，整个问题也就得到解决了。
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *head = NULL;
ListNode* p = pHead;
while(p){
ListNode *temp = new ListNode(p->val);
temp->next = head;
head = temp;
p = p->next;
}
return head;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！