You are given the head
of a linked list, and an integer k
.
Return the head of the linked list after swapping the values of the kth
node from the beginning and the kth
node from the end (the list is 1-indexed).
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]
Example 2:
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5 Output: [7,9,6,6,8,7,3,0,9,5]
Example 3:
Input: head = [1], k = 1 Output: [1]
Example 4:
Input: head = [1,2], k = 1 Output: [2,1]
Example 5:
Input: head = [1,2,3], k = 2 Output: [1,2,3]
Constraints:
n
.1 <= k <= n <= 105
0 <= Node.val <= 100
struct Solution;
use rustgym_util::*;
impl Solution {
fn swap_nodes(head: ListLink, k: i32) -> ListLink {
let mut p = head;
let mut nodes: Vec<Box<ListNode>> = vec![];
let k = k as usize;
while let Some(mut node) = p {
p = node.next.take();
nodes.push(node);
}
let n = nodes.len();
nodes.swap(k - 1, n - k);
let mut prev = None;
while let Some(mut node) = nodes.pop() {
node.next = prev;
prev = Some(node);
}
prev
}
}
#[test]
fn test() {
let head = list!(1, 2, 3, 4, 5);
let k = 2;
let res = list!(1, 4, 3, 2, 5);
assert_eq!(Solution::swap_nodes(head, k), res);
let head = list!(7, 9, 6, 6, 7, 8, 3, 0, 9, 5);
let k = 5;
let res = list!(7, 9, 6, 6, 8, 7, 3, 0, 9, 5);
assert_eq!(Solution::swap_nodes(head, k), res);
let head = list!(1);
let k = 1;
let res = list!(1);
assert_eq!(Solution::swap_nodes(head, k), res);
let head = list!(1, 2);
let k = 1;
let res = list!(2, 1);
assert_eq!(Solution::swap_nodes(head, k), res);
let head = list!(1, 2, 3);
let k = 2;
let res = list!(1, 2, 3);
assert_eq!(Solution::swap_nodes(head, k), res);
}