Given an array arr[] of n elements in the following format {a1, a2, a3, a4, .., an/2, b1, b2, b3, b4, ., bn/2}, the task is shuffle the array to {a1, b1, a2, b2, a3, b3, , an/2, bn/2} without using extra space.
Example 1:
Input: n = 4, arr[] = {1, 2, 9, 15}
Output:  1 9 2 15
Explanation: a1=1 , a2=2 , b1=9 , b2=15
So the final array will be :  
a1, b1, a2, b2 = { 1, 9, 2, 15 }
Example 2:
Input: n = 6
arr[] = {1, 2, 3, 4, 5, 6}
Output: 1 4 2 5 3 6
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function shuffleArray() that takes array arr[], and an integer n as parameters and modifies the given array according to the above-given pattern.
 
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ n ≤ 10^{5}
0≤ arr[i]≤ 103

Difficulty: MEDIUM
Tags: Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Starter code:
class Solution:

    def shuffleArray(self, arr, n):

        # Your code goes here

Solutions:
class Solution:

	def shuffleArray(self, arr, n):
		l = []
		k = arr[:n // 2]
		j = arr[n // 2:]
		for i in range(len(k)):
			l.append(k[i])
			l.append(j[i])
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def shuffleArray(self, arr, n):
		arr1 = arr[:n // 2]
		arr2 = arr[n // 2:]
		for i in range(n):
			if i % 2 == 0:
				arr[i] = arr1.pop(0)
			elif i % 2 == 1:
				arr[i] = arr2.pop(0)
				arr.append('')
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		for i in range(n // 2):
			arr.append(arr[i])
			arr.append(arr[n // 2 + i])
		arr[:] = arr[n:]
		return arr


class Solution:

	def r_shuffle(self, arr1, arr2, n, result):
		if len(arr1) == len(arr2) == 1:
			result.extend([arr1[0], arr2[0]])
		else:
			m = n // 2
			self.r_shuffle(arr1[0:m], arr2[0:m], m, result)
			self.r_shuffle(arr1[m:], arr2[m:], len(arr1[m:]), result)

	def shuffleArray(self, arr, n):
		result = []
		middleI = n // 2
		self.r_shuffle(arr[0:middleI], arr[middleI:], middleI, result)
		for i in range(n):
			arr[i] = result[i]


class Solution:

	def shuffleArray(self, arr, n):
		d = n // 2
		for i in range(1, n - 2, 2):
			arr.insert(i, arr[d])
			arr.pop(d + 1)
			d += 1


class Solution:

	def shuffleArray(self, arr, n):
		a = arr[0:n // 2]
		b = arr[n // 2:]
		c1 = 0
		c2 = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = a[c1]
				c1 += 1
			else:
				arr[i] = b[c2]
				c2 += 1


class Solution:

	def shuffleArray(self, arr, n):
		arr[:] = [item for pair in zip(arr[:n // 2], arr[n // 2:]) for item in pair]


class Solution:

	def shuffleArray(self, arr, n):
		a = len(arr)
		for i in range(1, a, 2):
			arr.insert(i, None)
		for i in range(a // 2):
			arr[2 * i + 1] = arr[a + i]
		for i in range(a // 2):
			arr.pop()
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		i = 0
		mid = n // 2
		j = mid
		arr1 = [0] * n
		m = 0
		while i < mid and j < n:
			arr1[m] = arr[i]
			i += 1
			m += 1
			arr1[m] = arr[j]
			j += 1
			m += 1
		for i in range(n):
			arr[i] = arr1[i]
		return arr


class Solution:
	x = 0

	def solve(self, i, arr, n):
		if i == n // 2 - 1:
			return
		a = arr[i - n // 2]
		b = arr[i]
		self.solve(i - 1, arr, n)
		arr[i - n // 2 + self.x] = a
		arr[i - n // 2 + 1 + self.x] = b
		self.x += 1

	def shuffleArray(self, arr, n):
		i = 1
		j = n // 2
		ans = [0 for _ in range(n)]
		ans[0] = arr[0]
		ans[n - 1] = arr[n - 1]
		k = 1
		while i < n // 2 and j < n:
			ans[k] = arr[j]
			k = k + 1
			ans[k] = arr[i]
			k = k + 1
			i = i + 1
			j = j + 1
		for i in range(n):
			arr[i] = ans[i]
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		ans = [0] * n
		k = 0
		for i in range(0, n // 2):
			ans[k] = arr[i]
			k += 1
			ans[k] = arr[n // 2 + i]
			k += 1
		return ans


class Solution:

	def shuffleArray(self, arr, n):
		if len(arr) == 1:
			return 0
		else:
			if n % 2 == 0:
				mini = arr[0:n // 2]
				maxi = arr[n // 2:n]
			arr.clear()
			lmin = len(mini)
			lmax = len(maxi)
			for i in range(lmax):
				arr.append(mini[i])
				arr.append(maxi[i])
			if lmin > lmax:
				arr.extend(maxi[lmax:lmin])


class Solution:

	def shuffleArray(self, arr, n):
		k = list(arr)
		a = 1
		b = len(k) // 2
		for i in range(1, len(arr) - 1, 2):
			arr[i] = k[b]
			arr[i + 1] = k[a]
			b += 1
			a += 1


class Solution:

	def shuffleArray(self, arr, n):
		x = n // 2
		l = arr[:x]
		r = arr[x:]
		flg = 0
		j = 0
		k = 0
		for i in range(n):
			if flg == 0:
				arr[i] = l[j]
				j += 1
				flg = 1
			else:
				arr[i] = r[k]
				k += 1
				flg = 0


class Solution:

	def shuffleArray(self, arr, n):
		mid = n // 2
		p = []
		first = 0
		second = n // 2
		for index in range(n):
			if index % 2 == 0:
				p.append(arr[first])
				first += 1
			else:
				p.append(arr[second])
				second += 1
		arr[:] = p


class Solution:

	def shuffleArray(self, arr, n):
		mid = n // 2
		a = arr[:mid]
		b = arr[mid:]
		arr[0::2] = a
		arr[1::2] = b
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		a = arr[:n // 2]
		b = arr[n // 2:]
		res = []
		for i in range(n // 2):
			res.append(a[i])
			res.append(b[i])
		arr[:] = res


class Solution:

	def shuffleArray(self, arr, n):
		l = len(arr)
		p = [0] * l
		for i in range(l):
			if i < l // 2:
				pos = i
				pos = 2 * pos
				p[pos] = arr[i]
			else:
				pos = i
				pos = 2 * (pos - n) + 1
				p[pos] = arr[i]
		for i in range(l):
			arr[i] = p[i]


class Solution:

	def shuffleArray(self, arr, n):
		half = n // 2
		frist_half = arr[:half]
		second_half = arr[half:]
		del arr[:]
		for i in range(half):
			arr.append(frist_half[i])
			arr.append(second_half[i])
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		half = n // 2
		l1 = arr[0:half]
		l2 = arr[half:n]
		del arr[:]
		for i in range(half):
			arr.append(l1[i])
			arr.append(l2[i])


class Solution:

	def shuffleArray(self, arr, n):
		mid = n // 2
		k = mid
		i = 1
		while mid < n:
			arr.insert(i, arr[mid])
			arr.pop(mid + 1)
			i += 2
			mid += 1


class Solution:

	def shuffleArray(self, arr, n):
		a = arr[:n // 2]
		b = arr[n // 2:]
		arr.clear()
		for i in range(n // 2):
			arr.append(a[i])
			arr.append(b[i])
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		res = []
		l = 0
		r = n // 2
		for i in range(n):
			if i % 2 == 0:
				res.append(arr[l])
				l += 1
			else:
				res.append(arr[r])
				r += 1
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def shuffleArray(self, arr, n):
		l = []
		mid = n / 2
		a1 = arr[:int(mid)]
		a2 = arr[int(mid):]
		for i in range(len(a2)):
			l.append(a1[i])
			l.append(a2[i])
		for i in range(n):
			arr[i] = l[i]
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		L = n // 2
		l1 = arr[0:L]
		l2 = arr[L:n]
		a = []
		for i in range(L):
			a.append(l1[i])
			a.append(l2[i])
		arr.clear()
		arr.extend(a)
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		x = len(arr) // 2
		y = arr[x:]
		z = arr[:x]
		ans = []
		arr.clear()
		for i in range(x):
			ans.append(z[i])
			ans.append(y[i])
		arr.extend(ans)
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		l1 = arr[:int(n // 2)]
		l2 = arr[int(n // 2):]
		arr.clear()
		for i in range(int(n / 2)):
			arr.append(l1[i])
			arr.append(l2[i])
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		mid = n // 2
		for i in range(mid):
			x = arr.pop(i + mid)
			arr.insert(2 * i + 1, x)
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		a = []
		b = []
		for i in range(n):
			if i < n // 2:
				a.append(arr[i])
			elif i >= n // 2:
				b.append(arr[i])
		r = []
		for k in range(n // 2):
			r.append(a[k])
			r.append(b[k])
		arr[:] = r[:]


class Solution:

	def shuffleArray(self, arr, n):
		lis = []
		(s, m) = (0, len(arr) // 2)
		while s < len(arr) // 2:
			lis.append(arr[s])
			lis.append(arr[m])
			s += 1
			m += 1
		for i in range(len(arr)):
			arr[i] = lis[i]


class Solution:

	def shuffleArray(self, arr, n):
		a2 = []
		for k in range(int(n / 2)):
			a2.append(arr[k])
			a2.append(arr[int(n / 2 + k)])
		i = 0
		for k in a2:
			arr[i] = k
			i += 1


class Solution:

	def shuffleArray(self, arr, n):
		t = n // 2
		if n % 2 != 0:
			t = t + 1
		l = arr[:t]
		f = arr[t:]
		if n % 2 != 0:
			k = 0
			for i in range(0, t - 1):
				arr[k] = l[i]
				arr[k + 1] = f[i]
				k = k + 2
			arr[-1] = l[-1]
		else:
			k = 0
			for i in range(0, t):
				arr[k] = l[i]
				arr[k + 1] = f[i]
				k = k + 2


class Solution:

	def shuffleArray(self, arr, n):
		a = list()
		b = list()
		for i in range(0, int(n / 2)):
			a.append(arr[i])
		for i in range(int(n / 2), n):
			b.append(arr[i])
		for i in range(0, n):
			if i % 2 == 0:
				arr[i] = a[int(i / 2)]
			else:
				arr[i] = b[int(i / 2)]


class Solution:

	def shuffleArray(self, arr, n):
		l = n // 2
		p = []
		q = []
		for i in range(l):
			p.append(arr[i])
		for i in range(l, n):
			q.append(arr[i])
		arr[0] = p[0]
		px = 1
		qx = 0
		for i in range(1, n):
			if i % 2 != 0:
				arr[i] = q[qx]
				qx += 1
			else:
				arr[i] = p[px]
				px += 1
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		l = []
		x = n // 2
		for i in range(x):
			print
			l.extend([arr[i], arr[i + x]])
		arr[:] = l


class Solution:

	def shuffleArray(self, arr, n):

		def _solve(L, R):
			if R - L <= 1:
				return
			M = R - L + 1
			h = M // 2
			hh = h // 2
			if h % 2:
				(i, j, pv) = (L + hh, L + h, arr[L + h - 1])
				while i < L + h - 1:
					arr[i + hh] = arr[i]
					arr[i] = arr[j]
					i += 1
					j += 1
				arr[L + h + hh - 1] = pv
				_solve(L, L + hh + hh - 1)
				_solve(L + hh + hh, R)
			else:
				(i, j) = (L + hh, L + h)
				while i < L + h:
					(arr[i], arr[j]) = (arr[j], arr[i])
					i += 1
					j += 1
				_solve(L, L + h - 1)
				_solve(L + h, R)
		_solve(0, n - 1)


class Solution:

	def shuffleArray(self, arr, n):
		p = n // 2
		for i in range(0, p):
			t = arr.pop(0)
			arr.append(t)
			r = arr.pop(p - i - 1)
			arr.append(r)
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		for i in range(n // 2):
			arr[i] += arr[n // 2 + i] * 10000
		for i in range(n // 2 - 1, -1, -1):
			arr[2 * i + 1] = arr[i] // 10000
			arr[2 * i] = arr[i] % 10000


class Solution:

	def shuffleArray(self, arr, n):
		arr1 = arr[:n // 2]
		arr2 = arr[n // 2:]
		arr[::2] = arr1
		arr[1::2] = arr2
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		(center, odd_condition) = (n // 2, 1) if n % 2 == 0 else (n // 2 + 1, 0)
		b1_array = arr[center:]
		a1_array = arr[:center]
		a1_count = 0
		b1_count = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = a1_array[a1_count]
				a1_count += 1
			else:
				arr[i] = b1_array[b1_count]
				b1_count += 1


class Solution:

	def shuffleArray(self, arr, n):
		l = []
		l1 = arr[:n // 2]
		l2 = arr[n // 2:]
		for i in range(len(l1)):
			l.append(l1[i])
			l.append(l2[i])
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def shuffleArray(self, arr, n):
		m = n // 2
		l = []
		l1 = []
		for i in range(m):
			l.append(arr[i])
		for i in range(m, n):
			l1.append(arr[i])
		arr[::2] = l[:]
		arr[1::2] = l1[:]
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		d = []
		d += arr
		arr.clear()
		for i in range(n // 2):
			arr.append(d[i])
			arr.append(d[i + n // 2])


class Solution:

	def shuffleArray(self, arr, n):
		i = 0
		p = []
		k = len(arr) // 2
		j = k
		while j < n and i < k:
			p.append(arr[i])
			p.append(arr[j])
			i += 1
			j += 1
		a[:] = p


class Solution:

	def shuffleArray(self, arr, n):
		l = arr.copy()
		i = 0
		c = 0
		while i < len(arr):
			arr[i] = l[c]
			arr[i + 1] = l[n // 2 + c]
			c += 1
			i += 2
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		k = n // 2
		l = arr[:k]
		p = arr[k:]
		arr.clear()
		for i in range(len(p)):
			arr.append(l[i])
			arr.append(p[i])
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		k = n // 2
		h1 = arr[:k]
		h2 = arr[k:]
		arr.clear()
		for i in range(n // 2):
			arr += [h1[i]]
			arr += [h2[i]]
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		ans = []
		mid = n // 2
		for i in range(n // 2):
			ans.append(arr[i])
			ans.append(arr[i + mid])
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def shuffleArray(self, arr, n):
		b = arr[0:n // 2]
		c = arr[n // 2:len(arr)]
		d = []
		for i in range(len(b)):
			d.append(b[i])
			d.append(c[i])
		for i in range(len(arr)):
			arr[i] = d[i]
		return arr


class Solution:

	def shuffleArray(self, arr, n):
		k = n // 2
		a = []
		for i in range(n // 2):
			a.append(arr[i])
			a.append(arr[i + k])
		for i in range(0, n):
			arr[i] = a[i]
		return arr