leetcode/
swap_nodes_in_pairs.rs

1//! # 24. Swap Nodes in Pairs
2//!
3//! Medium
4//!
5//! Given a linked list, swap every two adjacent nodes and return its head.
6//! You must solve the problem without modifying the values in the list's nodes
7//! (i.e., only nodes themselves may be changed.)
8//!
9//! ## Example 1:
10//!
11//! Input: head = [1,2,3,4]
12//!
13//! Output: [2,1,4,3]
14
15// Definition for singly-linked list.
16// #[derive(PartialEq, Eq, Clone, Debug)]
17// pub struct ListNode {
18//   pub val: i32,
19//   pub next: Option<Box<ListNode>>
20// }
21//
22// impl ListNode {
23//   #[inline]
24//   fn new(val: i32) -> Self {
25//     ListNode {
26//       next: None,
27//       val
28//     }
29//   }
30// }
31
32use crate::ListNode;
33
34pub struct Solution;
35
36impl Solution {
37    pub fn swap_pairs(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
38        if head.is_none() {
39            return None;
40        }
41
42        let mut cur = &mut head;
43
44        // 1 -> 2 -> 3 -> 4
45        // ^
46        // cur
47        //      ^
48        //      first
49        //           ^
50        //           second
51        while cur.as_ref().is_some_and(|n| n.next.is_some()) {
52            let mut first = cur.as_mut().unwrap().next.take();
53            let second = first.as_mut().unwrap().next.take();
54
55            // swap
56            cur.as_mut().unwrap().next = second;
57            first.as_mut().unwrap().next = cur.take();
58            cur.replace(first.unwrap());
59
60            // next iteration
61            cur = &mut cur.as_mut().unwrap().next.as_mut().unwrap().next;
62        }
63
64        head
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use crate::util::linked_list::vec_to_list;
72
73    #[test]
74    fn test() {
75        let cases = vec![
76            (vec![], vec![]),
77            (vec![1], vec![1]),
78            (vec![1, 2], vec![2, 1]),
79            (vec![1, 2, 3], vec![2, 1, 3]),
80            (vec![1, 2, 3, 4], vec![2, 1, 4, 3]),
81            (vec![1, 2, 3, 4, 5], vec![2, 1, 4, 3, 5]),
82        ];
83        for (input, output) in cases {
84            let input = vec_to_list(input);
85            let output = vec_to_list(output);
86            assert_eq!(Solution::swap_pairs(input), output);
87        }
88    }
89}
leetcode/swap_nodes_in_pairs.rs

leetcode/
swap_nodes_in_pairs.rs
