leetcode-反转链表

点击:题目链接:反转一个单链表。

思路

使用迭代的方式,我们可以创建一个尾节点,然后将链表依次改变顺序,最后返回尾节点。

需要注意的是,当我们改变链表前部节点的引用关系时,需要创建一个临时节点来保存它的后面节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tail = NULL;

while(head){
ListNode* temp = head->next;
head->next = tail;
tail = head;
head = temp;
}
return tail;
}
};

复杂度

时间:O(N) 空间:O(1)

思路

由于该解题也包含层层递进的关系在里面,我们也可以尝试使用递归的方式。和迭代的方式不同,递归是从尾部节点开始置换。
我们需要不断遍历到链表的尾部,然后开始不断层层反转尾部链表。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head ==NULL || head->next == NULL){
return head;
}
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};

复杂度

时间:O(N), 空间:O(N)

作者

Dylan Zhu

发布于

2021-04-10

更新于

2021-04-10

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...