Given a Cirular Linked List of size N, split it into two halves circular lists. If there are odd number of nodes in the given circular linked list then out of the resulting two halved lists, first list should have one node more than the second list. The resultant lists should also be circular lists and not linear lists.
 
Example 1:
Input:
Circular LinkedList: 1->5->7
Output:
1 5
7
 
Example 2:
Input:
Circular LinkedList: 2->6->1->5
Output:
2 6
1 5
Your Task:
Your task is to complete the given function splitList(), which takes 3 input parameters: The address of the head of the linked list, addresses of the head of the first and second halved resultant lists and Set the head1_ref and head2_ref to the first resultant list and second resultant list respectively.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self):

        self.data = None

        self.next = None

'''



class Solution:

    def splitList(self, head, head1, head2):

        #code here

        

        

        #this is to emulate pass by reference in python please don't delete below line.

        return head1,head2

Solutions:
class Solution:

	def splitList(self, head, head1, head2):
		if head == None or head.next == head:
			return head
		count = 1
		head1 = head
		curr = head
		prev = None
		while curr.next != head:
			count += 1
			curr = curr.next
		prev = curr
		if count % 2 == 0:
			A = count // 2
			temp = head
			for i in range(A - 1):
				temp = temp.next
			head2 = temp.next
			temp.next = None
			temp.next = head1
			prev.next = head2
		else:
			A = count // 2
			temp = head
			for i in range(A):
				temp = temp.next
			head2 = temp.next
			temp.next = None
			temp.next = head1
			prev.next = None
			prev.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		node = head.next
		prev = head
		count = 1
		while head != node:
			prev = prev.next
			node = node.next
			count += 1
		if count % 2 == 0:
			count = count // 2
		else:
			count = count // 2 + 1
		node = head
		while count > 1:
			node = node.next
			count -= 1
		head1 = head
		head2 = node.next
		node.next = head1
		prev.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		if not head:
			return None
		slow = head
		fast = head.next
		while fast != head and fast.next != head:
			slow = slow.next
			fast = fast.next.next
		head1 = head
		head2 = slow.next
		slow.next = head1
		curr = head2
		while curr.next != head:
			curr = curr.next
		curr.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		fast = head
		slow = head
		while fast.next != head and fast.next.next != head:
			fast = fast.next.next
			slow = slow.next
		head1 = head
		head2 = slow.next
		slow.next = head1
		front = head2
		while front.next != head:
			front = front.next
		front.next = head2
		return (head1, head2)


import math

class Solution:

	def splitList(self, head, head1, head2):
		s = set()
		itr = head
		l = 0
		while itr not in s:
			s.add(itr)
			itr = itr.next
			l += 1
		hlf = math.ceil(l / 2)
		(itr, head1, k) = (head, head, 0)
		while k < hlf - 1:
			itr = itr.next
			k += 1
		nxt = itr.next
		head2 = nxt
		itr.next = None
		itr.next = head
		k = 0
		while k < l - hlf - 1:
			nxt = nxt.next
			k += 1
		nxt.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head.next
		head1 = head
		while slow and fast and fast.next:
			if fast == head or fast.next == head:
				head2 = slow.next
				slow.next = head
				break
			else:
				slow = slow.next
				fast = fast.next.next
		temp = head2
		while temp.next != head:
			temp = temp.next
		temp.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		count = 1
		tmp = head.next
		while tmp != head:
			count += 1
			tmp = tmp.next
		if count % 2 == 0:
			count = count / 2
		else:
			count = int(count / 2) + 1
		tmp = head
		head1 = head
		ct = 1
		while ct < count:
			ct += 1
			tmp = tmp.next
		head2 = tmp.next
		tmp.next = head1
		tmp = head2
		while tmp.next != head:
			tmp = tmp.next
		tmp.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slowPtr = fastPtr = head
		while fastPtr.next != head and fastPtr.next.next != head:
			fastPtr = fastPtr.next.next
			slowPtr = slowPtr.next
		head2 = slowPtr.next
		slowPtr.next = head
		head1 = head
		trav = head2
		while trav.next != head:
			trav = trav.next
		trav.next = head2
		return (head1, head2)


class Node:

	def __init__(self):
		self.data = None
		self.next = None

class Solution:

	def splitList(self, head, head1, head2):
		n = head
		L = []
		while n.next != head:
			L.append(n.data)
			n = n.next
		L.append(n.data)
		if len(L) % 2 == 0:
			l = int(len(L) // 2) - 1
		else:
			l = int(len(L) // 2)
		head1 = head
		n1 = head1
		while l != 0:
			n1 = n1.next
			l = l - 1
		head2 = n1.next
		n1.next = head
		n.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, h, h1, h2):
		f = h
		c = 1
		h1 = h2 = t = h
		while f.next != h:
			f = f.next
			c += 1
		if c % 2 == 0:
			c = c // 2
		else:
			c = c // 2 + 1
		while c != 0:
			t = h2
			h2 = h2.next
			c -= 1
		t.next = h1
		f.next = h2
		return (h1, h2)


class Solution:

	def splitList(self, head, head1, head2):
		length = 0
		curr = head
		while curr != None:
			length += 1
			if curr.next == head:
				break
			curr = curr.next
		m = length // 2
		if length % 2 != 0:
			m += 1
		head1 = None
		head2 = None
		head1 = head
		curr = head
		count = 0
		while curr != None:
			count += 1
			if count == m:
				temp = curr
				curr = curr.next
				temp.next = head1
				break
			curr = curr.next
		head2 = curr
		while curr != None:
			count += 1
			if count == length:
				curr.next = head2
				break
			curr = curr.next
		return (head1, head2)


class Solution:

	def show(self, head):
		current = head
		while current.next != None:
			print(current.data)
			current = current.next

	def length_of_linklist(self, head):
		tmp = head
		current = head.next
		lth = 1
		while True:
			if tmp == current:
				return (lth, last)
			lth += 1
			last = current
			current = current.next

	def splitList(self, head, head1, head2):
		(lth, last_node) = self.length_of_linklist(head)
		last_node.next = None
		slow = head
		fast = head
		while fast != None and fast.next != None:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		if lth % 2 == 0:
			mid = prev
		head1 = head
		head2 = mid.next
		mid.next = head1
		last_node.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(head1, head2) = (head, head)
		(ptr1, ptr2) = (head, head)
		while ptr2.next != head:
			ptr2 = ptr2.next
		ptr2.next = None
		ptr2 = head
		while ptr2 and ptr2.next:
			ptr1 = ptr1.next
			ptr2 = ptr2.next
			ptr2 = ptr2.next if ptr2 else ptr2
		head2 = ptr1.next if ptr2 else ptr1
		(ptr1, ptr2) = (head1, head2)
		while ptr1.next != ptr2:
			ptr1 = ptr1.next
		ptr1.next = head1
		while ptr2.next:
			ptr2 = ptr2.next
		ptr2.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		temp = head
		c = 1
		while temp.next != head:
			c += 1
			temp = temp.next
		temp1 = head
		if c % 2 == 0:
			c = c // 2
			i = 1
			while i != c:
				temp1 = temp1.next
				i += 1
			const = temp1.next
			temp1.next = head
			head1 = head
			temp.next = const
			head2 = const
		else:
			c = c // 2 + 1
			i = 1
			while i != c:
				temp1 = temp1.next
				i += 1
			const = temp1.next
			temp1.next = head
			head1 = head
			temp.next = const
			head2 = const
		return (head1, head2)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def splitList(self, head, head1, head2):
		if head is None:
			return (head1, head2)
		slow = head
		fast = head
		while fast.next != head and fast.next.next != head:
			slow = slow.next
			fast = fast.next.next
		if fast.next.next == head:
			fast = fast.next
		head1 = head
		head2 = slow.next
		slow.next = head1
		fast.next = head2
		return (head1, head2)


import math

class Solution:

	def splitList(self, head, head1, head2):
		p = head
		q = head
		if head.next == None:
			return (head, head)
		count = 0
		while p:
			count += 1
			q = p
			p = p.next
			if p == head:
				q.next = None
				break
		count = math.ceil(count / 2)
		p = head
		r = head
		while count != 0:
			r = p
			p = p.next
			count -= 1
		r.next = head
		q.next = p
		head1 = head
		head2 = p
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(temp1, temp2) = (head, head.next)
		while temp2 != head and temp2.next != head:
			temp1 = temp1.next
			temp2 = temp2.next.next
		head1 = head
		head2 = temp1.next
		if temp2.next == head:
			temp2.next = temp1.next
		else:
			pre = None
			new = temp1.next
			while new != head:
				pre = new
				new = new.next
			pre.next = temp1.next
		temp1.next = head
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		cur = temp = head
		c = 0
		l = []
		while cur not in l:
			l.append(cur)
			prev = cur
			cur = cur.next
			c += 1
		prev.next = None
		head1 = cur
		if c % 2 == 0:
			i = c // 2
		else:
			i = c // 2 + 1
		j = 0
		while j < i:
			j += 1
			prev = cur
			cur = cur.next
		prev.next = head1
		head2 = cur
		while cur != None:
			prev = cur
			cur = cur.next
		prev.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(tmp, t) = (head, head)
		n = 0
		while t.next != head:
			n += 1
			t = t.next
		n = n // 2
		head1 = tmp
		while n:
			n -= 1
			tmp = tmp.next
		head2 = tmp.next
		tmp.next = head
		tmp = head2
		while 1:
			if tmp.next == head:
				tmp.next = head2
				break
			tmp = tmp.next
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		temp = slow = fast = head
		slow_left = None
		fast_left = None
		if head == None:
			head1 = None
			head2 = None
			return (head1, head2)
		traversed = True
		while temp != fast and temp != fast.next or traversed:
			traversed = False
			slow_left = slow
			slow = slow.next
			fast_left = fast.next
			fast = fast.next.next
		if temp == fast.next:
			head2 = slow.next
			fast.next = slow.next
			slow.next = head
			head1 = head
		if temp == fast:
			slow_left.next = head
			head1 = head
			head2 = slow
			fast_left.next = slow
		return (head1, head2)


class Solution:

	def splitList(self, head, a, b):
		slow = head
		fast = head.next
		a = head
		while fast != head and fast.next != head:
			slow = slow.next
			fast = fast.next.next
		b = slow.next
		slow.next = head
		p = b
		while p.next != head:
			p = p.next
		p.next = b
		return (a, b)


class Solution:

	def splitList(self, head, head1, head2):
		p = r = head
		q = head.next
		c = 1
		while True:
			if r.next != head:
				c += 1
				r = r.next
			else:
				break
		if c % 2 == 0:
			t = int(c / 2)
		else:
			t = int((c + 1) / 2)
		for i in range(t - 1):
			p = q
			q = q.next
		p.next = head
		r.next = q
		head1 = head
		head2 = q
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head.next
		while fast != head and fast.next != head:
			p = fast
			slow = slow.next
			fast = fast.next.next
		if p.next.next == head:
			fast = p.next
		a = slow.next
		slow.next = head
		fast.next = a
		head1 = head
		head2 = a
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head.next
		while fast != head and fast.next != head:
			fast = fast.next.next
			slow = slow.next
		aftermid = slow.next
		slow.next = head
		head1 = head
		temp = aftermid
		while temp.next != head:
			temp = temp.next
		temp.next = aftermid
		head2 = aftermid
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(head1, head2) = (head, head)
		while head2.next is not head and head2.next.next is not head:
			head1 = head1.next
			head2 = head2.next.next
		if head2.next is not head:
			head2 = head2.next
		head2.next = head1.next
		head2 = head2.next
		head1.next = head
		head1 = head1.next
		return (head1, head2)


import math

class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head.next
		while fast != head and fast.next != head:
			slow = slow.next
			prev = fast.next
			fast = fast.next.next
		head1 = head
		head2 = slow.next
		slow.next = head
		if fast == head:
			prev.next = head2
		else:
			fast.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		s = head
		f = head
		count = 1
		while f is not None:
			f = f.next
			if f == head:
				break
			count += 1
		if count % 2 == 0:
			loop_c = count // 2
		else:
			loop_c = count // 2 + 1
		n = head
		head1 = n
		prev = None
		while loop_c:
			loop_c -= 1
			prev = n
			n = n.next
		prev.next = head
		head1 = head
		head2 = n
		p = head2
		prev = None
		while head2:
			prev = p
			p = p.next
			if head == p:
				break
		prev.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		start = head
		end = head
		while end.next != head and end.next.next != head:
			end = end.next.next
			start = start.next
		temp = start.next
		start.next = head
		head1 = head
		if end.next == head:
			end.next = temp
		else:
			end.next.next = temp
		head2 = temp
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		temp = head
		end1 = head
		N = 1
		end = head
		start = head
		while head:
			if head.next == start:
				break
			head = head.next
			N += 1
		end = head
		for i in range(N // 2 + N % 2 - 1):
			end1 = end1.next
		head2 = end1.next
		end.next = head2
		end1.next = start
		return (start, head2)


class Solution:

	def splitList(self, head, head1, head2):
		size = 1
		head2 = head1 = head
		while head:
			if head.next == head1:
				break
			head = head.next
			size += 1
		if size % 2 == 0:
			size -= 1
		for _ in range(size // 2):
			head2 = head2.next
		k = head2
		head2 = head2.next
		k.next = head1
		head.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		if head.next.next == None:
			node1 = head
			node2 = head.next
			node1.next = node1
			node2.next = node2
		slow = head
		fast = head
		while fast.next != head and fast.next.next != head:
			slow = slow.next
			fast = fast.next.next
		head1 = head
		head2 = slow.next
		slow.next = head
		temp = head2
		while temp.next != head:
			temp = temp.next
		temp.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		s = head
		f = head
		while f.next != head and f.next.next != head:
			s = s.next
			f = f.next.next
		if f.next.next == head:
			f = f.next
		head1 = head
		if head.next != head:
			head2 = s.next
		f.next = s.next
		s.next = head
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		fast = head
		slow = head
		while fast.next != head and fast.next.next != head:
			fast = fast.next.next
			slow = slow.next
		if fast.next.next == head:
			fast = fast.next
		fast.next = slow.next
		tmp = slow.next
		slow.next = head
		head1 = head
		head2 = tmp
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(slow, fast, prev) = (head, head, head)
		while True:
			prev = slow
			slow = slow.next
			fast = fast.next.next
			if fast == head or fast == head.next:
				break
		fast = slow
		while fast.next is not head:
			fast = fast.next
		(fast.next, prev.next) = (prev.next, head)
		head1 = head
		head2 = slow
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head.next
		while fast != head and fast.next != head:
			slow = slow.next
			fast = fast.next.next
		mid = slow
		head1 = head
		head2 = mid.next
		mid.next = head1
		tail = head2
		while tail.next != head:
			tail = tail.next
		tail.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		b = 0
		tmp = head
		while tmp.next != head:
			b += 1
			tmp = tmp.next
		c = b // 2
		head1 = head
		tmp = head
		i = 0
		prev = tmp
		while i < c:
			prev = tmp
			tmp = tmp.next
			i += 1
		head2 = tmp.next
		tmp.next = head1
		tmp = head2
		while tmp.next != head:
			tmp = tmp.next
		tmp.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		(nd, N) = (head.next, 1)
		while nd != head:
			N += 1
			nd = nd.next
		N1 = (N + 1) // 2
		N2 = N - N1
		head1 = head
		nd = head1
		for _ in range(N1 - 1):
			nd = nd.next
		head2 = nd.next
		nd.next = head1
		nd = head2
		for _ in range(N2 - 1):
			nd = nd.next
		nd.next = head2
		return (head1, head2)


import math

class Solution:

	def splitList(self, head, head1, head2):
		if head is None:
			return None
		count = 0
		current = head
		while current.next != head:
			count += 1
			current = current.next
		count += 1
		mid = math.ceil(count / 2)
		head1 = head
		current = head
		for i in range(mid - 1):
			current = current.next
		if head.next != head:
			head2 = current.next
		current.next = head1
		current2 = head2
		while current2.next != head:
			current2 = current2.next
		current2.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		n = 1
		t = head
		while t.next != head:
			n += 1
			t = t.next
		if n % 2 == 0:
			s = int((n - 1) / 2)
		else:
			s = int(n / 2)
		head1 = head
		t1 = head1
		for i in range(s):
			t1 = t1.next
		head2 = t1.next
		t1.next = head1
		t2 = head2
		while t2.next != head:
			t2 = t2.next
		t2.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow = head
		fast = head
		while fast.next != head:
			if fast.next.next == head:
				fast = fast.next
			else:
				fast = fast.next.next
				slow = slow.next
		head1 = head
		head2 = slow.next
		fast.next = slow.next
		slow.next = head
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		slow_ptr = head
		fast_ptr = head
		if head is None:
			return
		while fast_ptr.next != head and fast_ptr.next.next != head:
			fast_ptr = fast_ptr.next.next
			slow_ptr = slow_ptr.next
		if fast_ptr.next.next == head:
			fast_ptr = fast_ptr.next
		head1 = head
		if head.next != head:
			head2 = slow_ptr.next
		fast_ptr.next = slow_ptr.next
		slow_ptr.next = head
		return (head1, head2)
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		if head is None:
			return (None, None)
		count = 1
		temp = head
		while temp.next is not head:
			temp = temp.next
			count += 1
		mid_val = 0
		if count & 1:
			mid_val = count // 2 + 1
		else:
			mid_val = count // 2
		temp = head
		prev = Node()
		prev.next = head
		moving_counter = 0
		while moving_counter < mid_val:
			temp = temp.next
			moving_counter += 1
			prev = prev.next
		prev.next = head
		second_head = temp
		while temp.next is not head:
			temp = temp.next
		temp.next = second_head
		head1 = head
		head2 = second_head
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		if head is None:
			return (None, None)
		count = 1
		temp = head
		while temp.next is not head:
			count += 1
			temp = temp.next
		mid = count // 2
		if count % 2 != 0:
			mid += 1
		temp2 = head
		while mid != 1:
			temp2 = temp2.next
			mid -= 1
		head2 = temp2.next
		temp.next = head2
		temp2.next = head
		head1 = head
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		x = head
		y = head
		z = head.next
		pre = x
		pre1 = y
		while True:
			pre = x
			pre1 = y
			x = x.next
			y = y.next.next
			if y == head:
				pre1.next.next = x
				break
			if y == z:
				pre1.next = x
				break
		pre.next = head
		head1 = head
		head2 = x
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		curr = head.next
		n = 0
		while True:
			if curr != head:
				n += 1
			else:
				n += 1
				break
			curr = curr.next
		if n % 2 == 0:
			curr = head
			i = 1
			while i < n // 2:
				curr = curr.next
				i += 1
			head1 = head
			head2 = curr.next
			curr.next = head1
			curr = head2
			i = 1
			while i < n // 2:
				curr = curr.next
				i += 1
			curr.next = head2
		else:
			curr = head
			i = 1
			while i <= n // 2:
				curr = curr.next
				i += 1
			head1 = head
			head2 = curr.next
			curr.next = head1
			curr = head2
			i = 1
			while i < n // 2:
				curr = curr.next
				i += 1
			curr.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		head1 = head
		i = 2
		while head.next is not head1:
			head = head.next
			i += 1
		n = i // 2
		for _ in range(n):
			head = head.next
		head2 = head.next
		head.next = head1
		head = head2
		while head.next is not head1:
			head = head.next
		head.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		s = f = head
		if head.next == head or head == None:
			head1 = head
			head2 = None
			return (head1, head2)
		while f.next != head and f.next.next != head:
			s = s.next
			f = f.next.next
		mid = s
		head1 = head
		h2 = head2 = mid.next
		mid.next = head1
		temp = head
		while h2.next != head:
			h2 = h2.next
		h2.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		ptr = head
		count = 0
		while ptr.next != head:
			count += 1
			ptr = ptr.next
		count += 1
		mid = (count - 1) // 2
		head1 = head
		ptr = head
		while mid:
			ptr = ptr.next
			mid -= 1
		head2 = ptr.next
		ptr.next = head1
		ptr = head2
		while ptr.next != head:
			ptr = ptr.next
		ptr.next = head2
		return (head1, head2)


class Solution:

	def splitList(self, head, head1, head2):
		temp = head
		head1 = head
		count = 1
		while temp.next != head:
			count += 1
			temp = temp.next
		temp.next = None
		temp = head
		c = count // 2
		while c - 1:
			temp = temp.next
			c -= 1
		if count % 2 == 0:
			head2 = temp.next
			temp.next = head1
		else:
			head2 = temp.next.next
			temp.next.next = head1
		temp = head2
		while temp.next:
			temp = temp.next
		temp.next = head2
		return (head1, head2)