# Posts tagged as “swap”

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:

• The number of nodes in the list is n.
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

## Solution:

Two passes. First pass, find the length of the list. Second pass, record the k-th and n-k+1-th node.
Once done swap their values.

Time complexity: O(n)
Space complexity: O(1)

## C++

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.


Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.


Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

## Solution 1: Sort and check.

Time complexity: O(nlog)
Space complexity: O(1)

## Solution 2: Rearrange the array

Find min / max / diff and put each element into its correct position by swapping elements in place.

Time complexity: O(n)
Space complexity: O(1)

## C++

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].


Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].


Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

• 1 <= arr1.length, arr2.length <= 2000
• 0 <= arr1[i], arr2[i] <= 10^9

Solution: DP

Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)

## C++

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root.  Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyagewe are given.

If we can do so, then return a list of the values of all nodes flipped.  You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]


Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]


Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []


Note:

1. 1 <= N <= 100

## Solution: Pre-order traversal

if root->val != v[pos] return [-1]
if root->left?->val != v[pos + 1], swap the nodes

# Problem

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.

# Solution

Two passes.

First pass, get the length of the list.

Second pass, swap in groups.

Time complexity: O(n)

Space complexity: O(1)