1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

//! Reverse Nodes in k-Group [leetcode: reverse_nodes_in_k_group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
//!
//! Given a linked list, reverse the nodes of a linked list *k* at a time and return its modified list.
//!
//! *k* is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of *k* then left-out nodes in the end should remain as it is.
//!
//! **Example:**
//!
//! ```
//! Given this linked list: 1->2->3->4->5
//!
//! For k = 2, you should return: 2->1->4->3->5
//!
//! For k = 3, you should return: 3->2->1->4->5
//! ```
//!
//! **Note:**
//! * Only constant extra memory is allowed.
//! * You may not alter the values in the list's nodes, only nodes itself may be changed.
//!

/// # Solutions
///
/// # Approach 1: Recursion
///
/// * Time complexity: O(2n)
///
/// * Space complexity: O(n)
///
/// * Runtime: 0ms
///
/// Memory: 2.7MB
///
/// ```rust
///
/// // Definition for singly-linked list.
/// // #[derive(PartialEq, Eq, Clone, Debug)]
/// // pub struct ListNode {
/// //   pub val: i32,
/// //   pub next: Option<Box<ListNode>>
/// // }
/// //
/// // impl ListNode {
/// //   #[inline]
/// //   fn new(val: i32) -> Self {
/// //     ListNode {
/// //       next: None,
/// //       val
/// //     }
/// //   }
/// // }
/// impl Solution {
///     pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
///         let mut head = head;
///         let mut tail = &mut head;
///
///         for _ in 0..k {
///             match tail.as_mut() {
///                 None => return head,
///                 Some(tail_ref) => tail = &mut tail_ref.next,
///             }
///         }
///
///         let tail = tail.take();
///         Solution::add(head, Solution::reverse_k_group(tail, k))
///     }
///
///     pub fn add(head: Option<Box<ListNode>>, tail: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
///         let mut head = head;
///         let mut tail = tail;
///
///         while let Some(mut new_tail) = head.take() {
///             head = new_tail.next.take();
///             new_tail.next = tail.take();
///             tail = Some(new_tail);
///         }
///         tail
///     }
/// }
/// ```
///
pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
    let mut head = head;
    let mut tail = &mut head;

    for _ in 0..k {
        match tail.as_mut() {
            None => return head,
            Some(tail_ref) => tail = &mut tail_ref.next,
        }
    }

    let tail = tail.take();
    add(head, reverse_k_group(tail, k))
}

pub fn add(head: Option<Box<ListNode>>, tail: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut head = head;
    let mut tail = tail;

    while let Some(mut new_tail) = head.take() {
        head = new_tail.next.take();
        new_tail.next = tail.take();
        tail = Some(new_tail);
    }
    tail
}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>
}

#[allow(dead_code)]
impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val
        }
    }
}