2021/04/22
2021-04-22 rust 递归版
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if let Some(mut node) = head {
let next_node = node.next.take();
if next_node.is_none() {
return Some(node);
} else {
let mut n = Solution::reverse_list(next_node).unwrap();
let mut p = &mut n;
// 这个时候 next_node 其实已经是尾结点了，但是此时没有它的所有权了
while p.next.is_some() {
p = p.next.as_mut().unwrap();
}
p.next = Some(node);
return Some(n);
}
} else {
return None;
}
}
}
用 rust 写的这个递归版，性能比较差，耗时24ms，原因在于上面注释那里，每次还有去寻找反转之后的链表的尾结点。所以补一个 Java 版的。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
if (head.next == null) return head;
ListNode tail = head.next;
head.next = null;
ListNode newHead = reverseList(tail);
tail.next = head;
return newHead;
}
}
2021-04-23 rust 双指针版
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
return Self::reverse_list_2ptr(None, head);
}
fn reverse_list_2ptr(mut reversed: Option<Box<ListNode>>, mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
while let Some(ref mut node) = head {
let next_head = node.next.take();
node.next = reversed.take();
reversed = head.take();
head = next_head;
}
return reversed;
}
}
可以用 std::mem::replace 方法简化一点操作
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
return Self::reverse_list_2ptr(None, head);
}
fn reverse_list_2ptr(mut reversed: Option<Box<ListNode>>, mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
while let Some(ref mut node) = head {
let next_head = std::mem::replace(&mut node.next, reversed);
reversed = head;
head = next_head;
}
return reversed;
}
}
还是给一个 Java 双指针版本吧：
class Solution {
public ListNode reverse(ListNode head) {
ListNode left = null;
ListNode right = head;
while (right != null) {
ListNode newRight = right.next;
right.next = left;
left = right;
right = newRight;
}
return left;
}
}
2017-03-21 总结
方法一
递归版的写法，参考stackoverflow上面的这个回答,很有启发。
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL) return NULL;
if (head->next == NULL) return head;
struct ListNode* second = head->next;
head->next = NULL;
struct ListNode* reversedList = reverseList(second);
second->next = head;
return reversedList;
}
方法二
维护两个指针，指针rHead指向反后的链表的头结点，lHead指向的是待反转连标点头结点。
| 左边链表 | 右边链表 |
|---|---|
| null | a->b->c->null |
| null<-a | b->c->null |
| null<-a<-b | c->null |
| null<-a<-b<-c | null |
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *lHead = NULL;
struct ListNode *rHead = head;
while (rHead != NULL) {
struct ListNode *ptr = rHead->next;
rHead->next = lHead;
lHead = rHead;
rHead = ptr;
}
return lHead;
}
haskell版
学习上面的思想后用haskell实现了一个反转列表函数,虽然效率比较低
reverse1 [] = []
reverse1 (x:[]) = [x]
reverse1 (x:xs) = reverse1 xs ++ [xs]
实际上haskell自己是这么实现的
reverse :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse = foldl (flip (:)) []
#else
reverse l = rev l []
where
rev [] a = a
rev (x:xs) a = rev xs (x:a)
#endif