You are given a special linked list with N nodes where each node has a next pointer pointing to its next node. You are also given M random pointers, where you will be given M number of pairs denoting two nodes a and b  i.e. a->arb = b (arb is pointer to random node).
Construct a copy of the given list. The copy should consist of exactly N new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.arb --> Y, then for the corresponding two nodes x and y in the copied list, x.arb --> y.
Return the head of the copied linked list.
Note :- The diagram isn't part of any example, it just depicts an example of how the linked list may look like.
Example 1:
Input:
N = 4, M = 2
value = {1,2,3,4}
pairs = {{1,2},{2,4}}
Output: 1
Explanation: In this test case, there
are 4 nodes in linked list.  Among these
4 nodes,  2 nodes have arbitrary pointer
set, rest two nodes have arbitrary pointer
as NULL. Second line tells us the value
of four nodes. The third line gives the
information about arbitrary pointers.
The first node arbitrary pointer is set to
node 2.  The second node arbitrary pointer
is set to node 4.
Example 2:
Input:
N = 4, M = 2
value[] = {1,3,5,9}
pairs[] = {{1,1},{3,4}}
Output: 1
Explanation: In the given testcase ,
applying the method as stated in the
above example, the output will be 1.
Your Task:
The task is to complete the function copyList() which takes one argument the head of the linked list to be cloned and should return the head of the cloned linked list.
NOTE : 
1. If there is any node whose arbitrary pointer is not given then it's by default NULL. 
2. Your solution return an output 1 if your clone linked list is correct, else it returns 0.
3. Don't make any changes to the original linked list.
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 100
1 <= M <= N
1 <= a, b <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None

        self.arb=None

        

param: head:  head of linkedList to copy

return: the head of the copied linked list the #output will be 1 if successfully copied

'''

class Solution:

    #Function to clone a linked list with next and random pointer.

    def copyList(self, head):

        # code here

    



Solutions:
class Solution:

	def copyList(self, head):
		front = head
		while front is not None:
			node = Node(front.data)
			temp = front.next
			front.next = node
			front.next.next = temp
			front = temp
		front = head
		while front is not None:
			if front.arb is not None:
				front.next.arb = front.arb.next
			front = front.next.next
		res_head = None
		res = None
		front = head
		while front is not None:
			if res_head is None:
				res_head = front.next
				res = front.next
			else:
				res.next = front.next
				res = res.next
			front.next = front.next.next
			front = front.next
		return res_head


class Solution:

	def copyList(self, head):
		d = {None: None}
		curr = head
		while curr:
			d[curr] = Node(curr.data)
			curr = curr.next
		curr = head
		while curr:
			d[curr].next = d[curr.next]
			d[curr].arb = d[curr.arb]
			curr = curr.next
		return d[head]


class Solution:

	def copyList(self, head):
		if not head:
			return None
		t = head
		while t:
			x = Node(t.data)
			temp = t.next
			t.next = x
			x.next = temp
			t = temp
		t = head
		while t:
			if t.arb:
				t.next.arb = t.arb.next
			t = t.next.next
		new_head = head.next
		t = head
		while t:
			temp = t.next.next
			if temp:
				t.next.next = temp.next
				t.next = temp
			else:
				t.next.next = None
				t.next = None
			t = temp
		return new_head


class Solution:

	def copyList(self, head):
		if head is None:
			return None
		curr = head
		while curr is not None:
			newNode = Node(curr.data)
			newNode.next = curr.next
			curr.next = newNode
			curr = newNode.next
		curr = head
		while curr is not None:
			curr.next.arb = curr.arb.next if curr.arb else None
			curr = curr.next.next
		curr = head
		new_head = head.next
		while curr is not None:
			newNode = curr.next
			curr.next = newNode.next
			newNode.next = curr.next.next if curr.next else None
			curr = curr.next
		return new_head


class Solution:

	def copyList(self, head):
		n_head = Node(head.data)
		temp1 = head
		temp2 = n_head
		temp2.next = temp1.next
		temp1.next = temp2
		temp1 = temp2.next
		while temp1:
			t = Node(temp1.data)
			t.next = temp1.next
			temp1.next = t
			temp1 = t.next
		temp1 = head
		temp2 = n_head
		while temp1:
			if temp1.arb:
				temp2.arb = temp1.arb.next
			temp1 = temp2.next
			if temp1:
				temp2 = temp1.next
		temp1 = head
		temp2 = n_head
		while temp1:
			temp1.next = temp2.next
			temp1 = temp1.next
			if temp1:
				temp2.next = temp1.next
				temp2 = temp2.next
		return n_head


class Solution:

	def copyList(self, head):
		curr = head
		while curr:
			nxt = curr.next
			curr.next = Node(curr.data)
			curr.next.next = nxt
			curr = nxt
		curr = head
		while curr:
			if curr.next:
				curr.next.arb = curr.arb.next if curr.arb else None
			curr = curr.next.next
		curr = head
		cp = head.next
		tmp = cp
		while curr and cp:
			curr.next = curr.next.next
			cp.next = cp.next.next if cp.next else cp.next
			curr = curr.next
			cp = cp.next
		return tmp


class Solution:

	def copyList(self, head):
		if not head:
			return None
		old_new_map = {}
		new_head = Node(head.data)
		old_new_map[head] = new_head
		new_curr = new_head
		old_curr = head.next
		while old_curr:
			new_node = Node(old_curr.data)
			old_new_map[old_curr] = new_node
			new_curr.next = new_node
			new_curr = new_node
			old_curr = old_curr.next
		old_curr = head
		new_curr = new_head
		while old_curr:
			if old_curr.arb:
				new_curr.arb = old_new_map[old_curr.arb]
			old_curr = old_curr.next
			new_curr = new_curr.next
		return new_head