206. 反转链表
题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这个就是常规操作了，使用一个变量记录前驱pre，一个变量记录后继next.
不断更新 current.next=pre 就好了
关键点解析
- 链表的基本操作（交换）
- 虚拟节点dummy 简化操作
- 注意更新current和pre的位置， 否则有可能出现溢出
代码
语言支持：JS，C++
JavaScript Code：
/*
* @lc app=leetcode id=206 lang=javascript
*
* [206] Reverse Linked List
*
* https://leetcode.com/problems/reverse-linked-list/description/
*
* algorithms
* Easy (52.95%)
* Total Accepted: 532.6K
* Total Submissions: 1M
* Testcase Example: '[1,2,3,4,5]'
*
* Reverse a singly linked list.
*
* Example:
*
*
* Input: 1->2->3->4->5->NULL
* Output: 5->4->3->2->1->NULL
*
*
* Follow up:
*
* A linked list can be reversed either iteratively or recursively. Could you
* implement both?
*
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (!head || !head.next) return head;
let cur = head;
let pre = null;
while(cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};C++ Code：
/**
* 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* prev = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};拓展
通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行reverse操作。
由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归会导致爆栈，因此，现实中并不推荐使用递归方式来操作链表。
描述
- 除第一个节点外，递归将链表reverse
- 将第一个节点添加到已reverse的链表之后
这里需要注意的是，每次需要保存已经reverse的链表的头节点和尾节点
C++实现
// 普通递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tail = nullptr;
return reverseRecursive(head, tail);
}
ListNode* reverseRecursive(ListNode *head, ListNode *&tail) {
if (head == nullptr) {
tail = nullptr;
return head;
}
if (head->next == nullptr) {
tail = head;
return head;
}
auto h = reverseRecursive(head->next, tail);
if (tail != nullptr) {
tail->next = head;
tail = head;
head->next = nullptr;
}
return h;
}
};
// （类似）尾递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
return reverseRecursive(nullptr, head, head->next);
}
ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next)
{
if (next == nullptr) return head;
auto n = next->next;
next->next = head;
head->next = prev;
return reverseRecursive(head, next, n);
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录