2020/2/25

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
请你返回该链表所表示数字的 十进制值 。

示例

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

相关标签

链表

解题思路

• 算法：
  题目要求一次遍历，这里只考虑用迭代法完成实现。可以将整个链表看做是由三部分组成：
  1）位于左段的无需反转的部分；
  2）位于中段的需要反转的部分；
  3）位于右段的无需反转的部分。
  为了将各个部分连接起来，需要用四个指针分别记录第一段的结束位置，第二段的开始位置，第二段的结束位置以及第三段的开始位置。
  中间部分的反转可以被看做是将未反转的链表中的节点，不断的的添加到已反转的链表的尾部，最后当所有未反转的节点全部被添加到已反转的链表中时，将左端的链表的尾部连接上反转链表的头部，再将右段的未反转链表添加到反转链表的尾部。最终实现一次遍历反转指定部分链表。

• 复杂度分析：
  时间复杂度：一趟遍历，最坏情况O(N)
  空间复杂度：O(1)

源代码

type Link = Option<Box<ListNode>>;

impl Solution {
    pub fn reverse_between(head: Link, m: i32, n: i32) -> Link {
        let mut t = Some(Box::new(ListNode::new(-1)));
        t.as_mut().unwrap().next = head;
        let mut head = t;

        let (mut left, mut right) = (&mut head as *mut Link, &mut head as *mut Link);

        unsafe {
            let move_p = |mut x: *mut Link, n: i32| {
                for _ in 0..n {
                    if *x == None {
                        return x;
                    }
                    x = &mut (*x).as_mut().unwrap().next as *mut Link;
                }
                x
            };

            left = move_p(left, m-1);
            right = move_p(left, 1);

            if *right == None || m==n {
                return head.unwrap().next;
            }

            let mut rev: Link = None;
            let mut rev_p = &mut None as *mut Link;
            let mut first = rev_p;
            let mut right_list: Link = None;

            for i in 0..(n-m+1) {
                let right_next = (*move_p(right, 1)).take();
                let mut t = (*right).take();
                t.as_mut().unwrap().next = (*rev_p).take();
                rev = t;
                rev_p = &mut rev as *mut Link;
                if i == 1 {
                    first = move_p(rev_p, 1);
                }
                right_list = right_next;
                right = &mut right_list as *mut Link;
            }

            (*left).as_mut().unwrap().next = (*rev_p).take();
            (*first).as_mut().unwrap().next = (*right).take();
        }

        head.unwrap().next
    }
}

执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.1MB, 在所有 Rust 提交中击败了100.00%的用户

总结

注意使用裸指针的时候，一定避免指向临时变量。当作用域结束，临时变量空间被释放，裸指针会指向不可控的位置。另外，在修改next指向的位置时，还记得需要利用take或者replace将next位置原本的对象提取出来，以免被覆盖。