题目地址
https://leetcode.com/problems/reverse-linked-list/description/
题目描述
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?
思路
这个就是常规操作了,使用一个变量记录前驱pre,一个变量记录后继next.
不断更新current.next = pre
就好了
关键点解析
- 链表的基本操作(交换)
- 虚拟节点dummy 简化操作
- 注意更新current和pre的位置, 否则有可能出现溢出
代码
语言支持:JS, C++, Python
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; } };
Python Code:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None prev = None cur = head while cur: cur.next, prev, cur = 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); } };
JavaScript实现
var reverseList = function(head) { // 递归结束条件 if (head === null || head.next === null) { return head } // 递归反转 子链表 let newReverseList = reverseList(head.next) // 获取原来链表的第2个节点newReverseListTail let newReverseListTail = head.next // 调整原来头结点和第2个节点的指向 newReverseListTail.next = head head.next = null // 将调整后的链表返回 return newReverseList }LeetCode题解1019.next-greater-node-in-linked-list
题目地址 https://leetcode-cn.com/problems/next-greater-node-in-linked-list/submissions/ 题目描述 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node_1, node_2, node_3, ... 。 每个节点都可能有下一个更大值(next larg…
LeetCode题解203.remove-linked-list-elements题目地址 https://leetcode.com/problems/remove-linked-list-elements/description/ 题目描述 Remove all elements from a linked list of integers that have value val. Example: Input: 1->2->…
与在Java中分配数组与分配链表相比,要使用多少内存? - java我的猜测是,存储在数组中的每个值都有32位/ 64位字(取决于CPU)。因此它将是数组大小X 32位/ 64位。对于链表,存储指向下一个元素的引用将是链接列表的两倍。因此它将是2 *数组大小X 32位/ 64位。这是正确的,我有什么遗漏吗? java大神给出的解决方案 多得多。链表中的每个元素都有:指向下一个元素的指针,指向上一个元素的指针,指向项目值的指针…
LeetCode题解150.evaluate-reverse-polish-notation题目地址 https://leetcode.com/problems/evaluate-reverse-polish-notation/description/ 题目描述 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are…
LeetCode题解190.reverse-bits题目地址 https://leetcode.com/problems/reverse-bits/description/ 题目描述 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111…