Given a linked list of characters and a string S.Return all the anagrams of the string present in the given linked list.In case of overlapping anagrams choose the first anagram from left.
Example 1:
Input: a -> b -> c -> a -> d -> b -> c -> a
S = bac
Output: [a -> b -> c, b -> c -> a]
Explanation: In the given linked list,
there are three anagrams: 
1. a -> b -> c -> a -> d -> b -> c -> a
2. a -> b -> c -> a -> d -> b -> c -> a
3. a -> b -> c -> a -> d -> b -> c -> a
But in 1 and 2, a -> b -> c and b -> c-> a
are ovelapping.So we take a -> b -> c as it
comes first from left.So the output is:
[a->b->c,b->c->a]
Example 2:
Input: a -> b -> d -> c -> a
S = bac
Output: -1 
Explanation: There is no anagrams, so output is -1
Your Task:
You don't need to read input or print anything. Your task is to complete the function findAnagrams() which takes head node of the linked list and a string S as input parameters and returns an array of linked list which only stores starting point of the Anagram. If there is no anagram in the linked list, leave the Array empty.
Expected Time Complexity: O(N), where N is length of LinkedList
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def findAnagrams(self, head, s):

        # code here

Solutions:
class Solution:

	def findAnagrams(self, head, s):
		Dout = dict()
		for b in s:
			Dout[b] = Dout.get(b, 0) + 1
		adv = head
		out = []
		Din = dict()
		while adv and adv.next:
			start = adv
			i = 0
			while i < len(s) and adv:
				Din[adv.data] = Din.get(adv.data, 0) + 1
				tail = adv
				adv = adv.next
				i += 1
			if Din == Dout:
				tail.next = None
				out.append(start)
				Din = dict()
			else:
				adv = start.next
				Din = dict()
		if out:
			return out
		a = Node()
		a.data = '-1'
		return [a]


class Solution:

	def anagram(self, smp, cmp):
		if len(smp) != len(cmp):
			return False
		for (k, v) in smp.items():
			if cmp.get(k) != v:
				return False
		return True

	def findAnagrams(self, head, s):
		ans = []
		prev = None
		smp = {}
		cmp = {}
		curr = head
		n = len(s)
		for i in range(n):
			if s[i] in smp:
				smp[s[i]] += 1
			else:
				smp[s[i]] = 1
		while curr != None:
			temp = curr
			for i in range(n):
				if temp == None:
					break
				if temp.data in cmp:
					cmp[temp.data] += 1
				else:
					cmp[temp.data] = 1
				prev = temp
				temp = temp.next
			if self.anagram(smp, cmp):
				prev.next = None
				ans.append(curr)
				curr = temp
			else:
				curr = curr.next
			cmp.clear()
		return ans


class Solution:

	def findAnagrams(self, head, s):
		d = {}
		for v in s:
			if v in d:
				d[v] += 1
			else:
				d[v] = 0
		count = len(s)
		temp = head
		i = 0
		l = []
		while temp != None and temp.next != None:
			temp1 = temp
			d1 = {}
			i = 0
			while i < count and temp != None:
				if temp.data in d1:
					d1[temp.data] += 1
				else:
					d1[temp.data] = 0
				temp2 = temp
				temp = temp.next
				i += 1
			if d1 == d:
				temp2.next = None
				l.append(temp1)
			else:
				temp = temp1.next
		if l:
			return l
		a = Node()
		a.data = '-1'
		l.append(a)
		return l


class Solution:

	def findAnagrams(self, head, s):
		Dout = dict()
		for b in s:
			Dout[b] = Dout.get(b, 0) + 1
		adv = head
		l = []
		Din = dict()
		while adv and adv.next:
			temp1 = adv
			i = 0
			while i < len(s) and adv:
				Din[adv.data] = Din.get(adv.data, 0) + 1
				temp2 = adv
				adv = adv.next
				i += 1
			if Din == Dout:
				temp2.next = None
				l.append(temp1)
				Din = dict()
			else:
				adv = temp1.next
				Din = dict()
		if l:
			return l
		a = Node()
		a.data = '-1'
		l.append(a)
		return l


class Solution:

	def checkAnagram(self, A, B):
		for i in range(26):
			if A[i] != B[i]:
				return False
		return True

	def checkAndPush(self, isAnagram, n, ptr1, ptr2, res, freq1):
		if isAnagram == False:
			return
		prev = None
		res.append(ptr1)
		temp = ptr2
		ptr2 = ptr2.next
		if temp != None:
			temp.next = None
		ptr1 = ptr2
		for i in range(26):
			freq1[i] = 0
		for i in range(n):
			if ptr2 != None:
				freq1[ord(ptr2.data) - ord('a')] += 1
				prev = ptr2
				if ptr2 != None:
					ptr2 = ptr2.next
		ptr2 = prev

	def findAnagrams(self, head, s):
		n = len(s)
		freq = [0] * 26
		for ch in s:
			freq[ord(ch) - ord('a')] += 1
		freq1 = [0] * 26
		ptr1 = head
		ptr2 = head
		prev = None
		for i in range(n):
			if ptr2 != None:
				freq1[ord(ptr2.data) - ord('a')] += 1
				prev = ptr2
				ptr2 = ptr2.next
		ptr2 = prev
		res = []
		while ptr2.next != None:
			ok = self.checkAnagram(freq1, freq)
			if ok:
				if ok == False:
					return
				prev = None
				res.append(ptr1)
				temp = ptr2
				ptr2 = ptr2.next
				if temp != None:
					temp.next = None
				ptr1 = ptr2
				for i in range(26):
					freq1[i] = 0
				for i in range(n):
					if ptr2 != None:
						freq1[ord(ptr2.data) - ord('a')] += 1
						prev = ptr2
						if ptr2 != None:
							ptr2 = ptr2.next
				ptr2 = prev
			else:
				freq1[ord(ptr1.data) - ord('a')] -= 1
				ptr1 = ptr1.next
				ptr2 = ptr2.next
				freq1[ord(ptr2.data) - ord('a')] += 1
		ok = self.checkAnagram(freq1, freq)
		if ok:
			res.append(ptr1)
		return res


class Solution:

	def findAnagrams(self, head, s):
		s = sorted(s)
		n = len(s)
		ans = []
		right_p = head
		curr_count = 0
		while right_p:
			if curr_count == 0:
				curr = []
				if right_p.data in s:
					dummy = right_p
					curr.append(right_p.data)
					curr_count += 1
				right_p = right_p.next
			elif curr_count < n - 1:
				if right_p.data in s:
					curr.append(right_p.data)
					curr_count += 1
					right_p = right_p.next
				else:
					right_p = dummy.next
					curr_count = 0
			else:
				curr.append(right_p.data)
				if sorted(''.join(curr)) == s:
					temp = right_p.next
					right_p.next = None
					ans.append(dummy)
					right_p = temp
				else:
					right_p = dummy.next
				curr_count = 0
		return ans


class Solution:

	def findAnagrams(self, head, s):
		ans = []
		(start, end) = (head, head)
		d = {}
		for i in s:
			d[i] = 1 + d.get(i, 0)
		cnt = len(d)
		cnt1 = 0
		d1 = {}
		while end:
			d1[end.data] = d1.get(end.data, 0) + 1
			if d.get(end.data, 0) == d1[end.data]:
				cnt1 += 1
			while d1[end.data] > d.get(end.data, 0):
				if d1[start.data] == d.get(start.data, 0):
					cnt1 -= 1
				d1[start.data] -= 1
				start = start.next
			if cnt == cnt1:
				ans.append(start)
				temp = end.next
				end.next = None
				start = temp
				end = temp
				d1.clear()
				cnt1 = 0
			else:
				end = end.next
		return ans


class Solution:

	def findAnagrams(self, head, s):
		ans = []
		ptr1 = head
		ptr2 = head
		prev = None
		hashString = [0] * 26
		for i in s:
			hashString[ord(i) - ord('a')] += 1
		hashAnagram = [0] * 26
		length = len(s)
		while length and ptr2:
			hashAnagram[ord(ptr2.data) - ord('a')] += 1
			prev = ptr2
			ptr2 = ptr2.next
			length -= 1
		ptr2 = prev
		while ptr2:
			if hashString == hashAnagram:
				ans.append(ptr1)
				ptr1 = ptr2.next
				ptr2.next = None
				ptr2 = ptr1
				hashAnagram = [0] * 26
				length = len(s)
				prev = None
				while length and ptr2:
					hashAnagram[ord(ptr2.data) - ord('a')] += 1
					prev = ptr2
					ptr2 = ptr2.next
					length -= 1
				ptr2 = prev
			else:
				hashAnagram[ord(ptr1.data) - ord('a')] -= 1
				ptr1 = ptr1.next
				prev = ptr2
				ptr2 = ptr2.next
				if ptr2:
					hashAnagram[ord(ptr2.data) - ord('a')] += 1
		if hashString == hashAnagram:
			ans.append(ptr1)
		return ans


class Solution:

	def findAnagrams(self, head, s):
		ans = []
		(start, end) = (head, head)
		n = len(s)
		mp1 = {}
		for c in s:
			mp1[c] = mp1.get(c, 0) + 1
		count1 = len(mp1)
		mp2 = {}
		count2 = 0
		while end:
			mp2[end.data] = mp2.get(end.data, 0) + 1
			if mp1.get(end.data, 0) == mp2[end.data]:
				count2 += 1
			while mp2[end.data] > mp1.get(end.data, 0):
				if mp2[start.data] == mp1.get(start.data, 0):
					count2 -= 1
				mp2[start.data] -= 1
				start = start.next
			if count2 == count1:
				ans.append(start)
				ahead = end.next
				end.next = None
				(start, end) = (ahead, ahead)
				mp2.clear()
				count2 = 0
			else:
				end = end.next
		return ans


class Solution:

	def findAnagrams(self, head, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		st = head
		en = head
		ans_list = []
		count = len(s)
		flag = False
		dcount = len(d)
		while st != None:
			if flag == False:
				if st.data in d:
					d[st.data] -= 1
					if d[st.data] == 0:
						dcount -= 1
						if dcount == 0:
							linked = Linked_List()
							i = en
							while i != st:
								linked.insert(i.data)
								i = i.next
							linked.insert(i.data)
							ans_list.append(linked.head)
							flag = True
				st = st.next
			if count <= 1:
				if en.data in d:
					if d[en.data] == 0:
						dcount += 1
					d[en.data] += 1
				en = en.next
				if en == st:
					flag = False
					count = len(s) + 1
			count -= 1
		return ans_list


from collections import Counter

class Solution:

	def findAnagrams(self, head, s):
		tail = head
		counter = Counter(s)
		totalCount = len(counter)
		tempTotalCount = 0
		tempCounter = counter.copy()
		anagrams = []
		while tail:
			if tail.data in tempCounter:
				tempCounter[tail.data] -= 1
				if tempCounter[tail.data] < 0:
					while tempCounter[tail.data] < 0:
						tempCounter[head.data] += 1
						if tempCounter[head.data] == 1:
							tempTotalCount -= 1
						head = head.next
				elif tempCounter[tail.data] == 0:
					tempTotalCount += 1
			else:
				head = tail.next
				tempTotalCount = 0
				tempCounter = counter.copy()
			if tempTotalCount == totalCount:
				anagrams.append(head)
				tempTotalCount = 0
				tempCounter = counter.copy()
				head = tail
				tail = tail.next
				head.next = None
				head = tail
			else:
				tail = tail.next
		return anagrams


class Solution:

	def findAnagrams(self, head, s):

		def newLL(head, tail):
			l1 = Linked_List()
			while head != tail.next:
				l1.insert(head.data)
				head = head.next
			return l1.head
		anagrams = list()
		s = sorted(s)
		tail = head
		k = len(s) - 1
		while tail and k:
			tail = tail.next
			k -= 1
		copy = head
		while tail:
			wind = list()
			while copy != tail.next:
				wind.append(copy.data)
				copy = copy.next
			if sorted(wind) == s:
				anagrams.append(newLL(head, tail))
				head = tail.next
				k = len(s)
				while tail and k:
					tail = tail.next
					k -= 1
			else:
				tail = tail.next
				head = head.next
			copy = head
		return anagrams


class Solution:

	def findAnagrams(self, head, s):
		N = len(s)
		TAR = [0] * 26
		for c in s:
			TAR[ord(c) - 97] += 1
		(ans, h, t, F) = ([], head, head, None)
		while t:
			if F is None:
				F = [0] * 26
				for _ in range(N):
					if t is None:
						break
					F[ord(t.data) - 97] += 1
					t = t.next
			else:
				F[ord(h.data) - 97] -= 1
				F[ord(t.data) - 97] += 1
				(h, t) = (h.next, t.next)
			if F == TAR:
				ans.append(h)
				while h.next != t:
					h = h.next
				h.next = None
				h = t
				F = None
		return ans


class Solution:

	def findAnagrams(self, head, s):
		slide = [0] * 26
		for i in s:
			slide[ord(i) - 97] += 1
		make = [0] * 26
		n = len(s)
		i = 0
		ans = []
		h = head
		prev = head
		while h:
			if i < n:
				make[ord(h.data) - 97] += 1
			elif slide == make:
				prev.next = None
				ans.append(head)
				head = h
				i = 0
				make = [0] * 26
				make[ord(h.data) - 97] += 1
			else:
				make[ord(head.data) - 97] -= 1
				make[ord(h.data) - 97] += 1
				head = head.next
			prev = h
			h = h.next
			i += 1
		if slide == make:
			prev.next = None
			ans.append(head)
		return ans


class Solution:

	def findAnagrams(self, head, s):
		mem = {}
		for letter in s:
			if letter not in mem:
				mem[letter] = 0
			mem[letter] += 1
		node = head
		ans = []
		while node is not None:
			currHead = node
			anchor = node
			prev = node
			newMem = mem.copy()
			i = 0
			nonLetter = False
			while currHead is not None and i < len(s):
				if currHead.data in newMem:
					newMem[currHead.data] -= 1
				else:
					nonLetter = True
					break
				prev = currHead
				currHead = currHead.next
				i += 1
			if nonLetter:
				node = currHead.next
			elif self.isAnagram(newMem):
				ans.append(anchor)
				prev.next = None
				node = currHead
			else:
				node = node.next
		return ans

	def isAnagram(self, dic):
		for value in dic.values():
			if value != 0:
				return False
		return True


class Solution:

	def findAnagrams(self, head, s):
		anagrams = []
		node = False
		num = 0
		l = []
		temp_annagram = False
		skip_ahead = 0
		while head is not None:
			temp_s = [i for i in s]
			if head.data in s:
				l.append(head.data)
				temp_s.remove(head.data)
				current_node = Node()
				current_node.data = head.data
				current_node.next = head.next
				temp_annagram = current_node
				next_node = current_node.next
				for _ in range(len(s)):
					if next_node is not None:
						new_node = Node()
						new_node.data = next_node.data
						new_node.next = next_node.next
						current_node.next = new_node
						current_node = new_node
						if next_node.data not in temp_s:
							l = []
							temp_annagram = False
							break
						else:
							l.append(next_node.data)
							temp_s.remove(next_node.data)
					else:
						l = []
						break
					if len(s) == len(l):
						current_node.next = None
						anagrams.append(temp_annagram)
						skip_ahead = len(s) - 1
						l = []
						break
					next_node = next_node.next
			if skip_ahead:
				while skip_ahead > 0:
					head = head.next
					skip_ahead -= 1
			head = head.next
		return anagrams


import copy

class Solution:

	def findAnagrams(self, head, s):
		h_map = dict()
		for i in range(0, len(s)):
			if s[i] not in h_map:
				h_map[s[i]] = 0
			h_map[s[i]] += 1
		org_map = copy.deepcopy(h_map)
		ans = []
		count = 0
		start = head
		node = head
		while node:
			if node.data in h_map:
				h_map[node.data] -= 1
				if h_map[node.data] == 0:
					count += 1
				while h_map[node.data] < 0:
					if h_map[start.data] == 0:
						count -= 1
					h_map[start.data] += 1
					start = start.next
				if count == len(h_map):
					ans.append(start)
					start = node.next
					new_node = node.next
					node.next = None
					node = new_node
					h_map = copy.deepcopy(org_map)
					count = 0
				else:
					node = node.next
			else:
				start = node.next
				count = 0
				h_map = copy.deepcopy(org_map)
				node = node.next
		return ans


class Solution:

	def findAnagrams(self, head, s):

		def isanagram(curr, need):
			for (k, v) in need.items():
				if k not in curr or curr[k] != need[k]:
					return False
			return True
		curr = {}
		need = {}
		n = len(s)
		for ch in s:
			need[ch] = 1 + need.get(ch, 0)
		p1 = p2 = head
		prev = None
		i = 0
		while i < n and p2 != None:
			curr[p2.data] = 1 + curr.get(p2.data, 0)
			i += 1
			prev = p2
			p2 = p2.next
		ans = []
		p2 = prev
		while p2.next != None:
			if isanagram(curr, need):
				ans.append(p1)
				t = p2
				p2 = p2.next
				t.next = None
				p1 = p2
				prev = None
				curr.clear()
				i = 0
				while i < n and p2 != None:
					curr[p2.data] = 1 + curr.get(p2.data, 0)
					i += 1
					prev = p2
					p2 = p2.next
				p2 = prev
			else:
				curr[p1.data] -= 1
				p1 = p1.next
				p2 = p2.next
				curr[p2.data] = 1 + curr.get(p2.data, 0)
		if isanagram(curr, need):
			ans.append(p1)
		return ans


from collections import Counter

class Solution:

	def findAnagrams(self, head, s):
		n = len(s)
		store = Counter(s)
		output = []
		head1 = head
		head2 = head
		for _ in range(n):
			store[head1.data] -= 1
			prev = head1
			head1 = head1.next
			if not head1:
				break
		while head1:
			if set(store.values()) == set([0]):
				start = Node()
				head = start
				for _ in range(n):
					head.next = Node()
					head = head.next
					head.data = head2.data
					head2 = head2.next
				output.append(start.next)
				head2 = head1
				store = Counter(s)
				for _ in range(n):
					store[head1.data] -= 1
					prev = head1
					head1 = head1.next
					if not head1:
						break
			else:
				store[head1.data] -= 1
				store[head2.data] += 1
				prev = head1
				head1 = head1.next
				head2 = head2.next
		if set(store.values()) == set([0]):
			start = Node()
			head = start
			for _ in range(n):
				head.next = Node()
				head = head.next
				head.data = head2.data
				head2 = head2.next
			output.append(start.next)
		return output


class Solution:

	def findAnagrams(self, head, s):
		n = len(s)
		arr = [0] * 26
		for i in s:
			arr[ord(i) - 97] += 1
		run = [0] * 26
		ans = []
		h = head
		t = head
		cnt = 0
		while h and t:
			ind = ord(t.data) - ord('a')
			run[ind] += 1
			cnt += 1
			if cnt > n:
				ind = ord(h.data) - ord('a')
				run[ind] -= 1
				cnt -= 1
				(h.next, h) = (None, h.next)
			if run == arr:
				(t.next, t) = (None, t.next)
				ans.append(h)
				run = [0] * 26
				cnt = 0
				h = t
			else:
				t = t.next
		return ans


class Solution:

	def findAnagrams(self, head, s):
		output = []
		n = len(s)
		s = list(s)
		s.sort()
		while head != None:
			if head.data in s:
				cur = head
				i = 0
				ss = []
				pre = cur
				while i < n and cur != None:
					ss.append(cur.data)
					pre = cur
					cur = cur.next
					i += 1
				if sorted(ss) == s:
					output.append(head)
					head = cur
					pre.next = None
				else:
					head = head.next
			else:
				head = head.next
		return output


class Solution:

	def findAnagrams(self, head, s):

		def check1(counts, window):
			for i in range(97, 123):
				cur = chr(i)
				if window.get(cur, 0) < counts.get(cur, 0):
					return False
			return True

		def check2(counts, window):
			for i in range(97, 123):
				cur = chr(i)
				if window[cur] != counts[cur]:
					return False
			return True
		res = []
		counts = {chr(i): 0 for i in range(97, 123)}
		for i in s:
			if i in s:
				counts[i] += 1
		window = {chr(i): 0 for i in range(97, 123)}
		prev = None
		ptr = head
		n = len(s)
		for i in range(n):
			if s[i] in window:
				window[ptr.data] += 1
			prev = ptr
			ptr = ptr.next
		beg = head
		while beg and ptr:
			if check2(counts, window):
				prev.next = None
				res.append(beg)
				x = beg
				window = {chr(i): 0 for i in range(97, 123)}
				beg = ptr
				for i in range(n):
					if not ptr:
						for i in res:
							ptr = i
							for i in range(n - 1):
								ptr = ptr.next
							ptr.next = None
						return res if res else -1
					window[ptr.data] += 1
					ptr = ptr.next
				continue
			window[ptr.data] += 1
			window[beg.data] -= 1
			beg = beg.next
			prev = ptr
			ptr = ptr.next
		if check2(counts, window):
			res.append(beg)
			prev.next = None
		for i in res:
			ptr = i
			for i in range(n - 1):
				ptr = ptr.next
			ptr.next = None
		return res


class Solution:

	def findAnagrams(self, head, s):
		sublists = []
		lowercase = 'abcdefghijklmnopqrstuvwxyz'
		character_counts = {character: 0 for character in lowercase}
		character_counts_desired = {character: 0 for character in lowercase}
		for character in s:
			character_counts_desired[character] += 1
		index = anagram_head = 0
		current_node = head
		for next_node in range(len(s) - 1):
			if not current_node:
				break
			character_counts[current_node.data] += 1
			current_node = current_node.next
		shift = 0
		previous_character = ''
		current_start = head
		while current_node:
			character_counts[current_node.data] += 1
			if previous_character:
				character_counts[previous_character] -= 1
			if shift:
				shift -= 1
			elif character_counts == character_counts_desired:
				sublists.append(current_start)
				shift = len(s) - 1
			previous_character = current_start.data
			current_start = current_start.next
			current_node = current_node.next
		for node in sublists:
			current_node = node
			for next_nodes in range(len(s) - 1):
				current_node = current_node.next
			current_node.next = None
		return sublists


from collections import Counter

class Solution:

	def match(self, s1, s2, _dict):
		if Counter(s1) == Counter(s2):
			if s2 in _dict:
				return False
			_dict[s2] = 1
			return True
		else:
			return False

	def printList(self, head):
		if head is not None:
			print(head.data + ' ', end='')
			head = head.next

	def addValue(self, head, n, res):
		new_node = Node()
		new_node.data = head.data
		res_head = new_node
		temp = head
		i = 0
		while i < n:
			new_node.next = Node()
			new_node = new_node.next
			new_node.data = temp.data
			temp = temp.next
			i += 1
		res.append(res_head)

	def findAnagrams(self, head, s):
		N = len(s)
		TAR = [0] * 26
		for c in s:
			TAR[ord(c) - 97] += 1
		(ans, h, t, F) = ([], head, head, None)
		while t:
			if F is None:
				F = [0] * 26
				for _ in range(N):
					if t is None:
						break
					F[ord(t.data) - 97] += 1
					t = t.next
			else:
				F[ord(h.data) - 97] -= 1
				F[ord(t.data) - 97] += 1
				(h, t) = (h.next, t.next)
			if F == TAR:
				ans.append(h)
				while h.next != t:
					h = h.next
				h.next = None
				h = t
				F = None
		return ans


class Solution:

	def findAnagrams(self, head, s):
		lengthS = len(s)
		s = sorted(s)
		data = []
		while head != None:
			data.append(head.data)
			head = head.next
		lengthH = len(data)
		res = []
		i = 0
		while i <= lengthH - lengthS:
			if sorted(data[i:i + lengthS]) == s:
				join = ' '.join(data[i:i + lengthS])
				jn = Node()
				jn.data = join
				res.append(jn)
				i += lengthS
				continue
			i += 1
		return res


class Solution:

	def findAnagrams(self, head, s):
		str_list = [0] * 26
		size = len(s)
		for it in s:
			str_list[ord(it) - ord('a')] += 1
		ll = [0] * 26
		res = []
		count = 0
		i = head
		j = head
		while j is not None:
			count += 1
			ll[ord(j.data) - ord('a')] += 1
			if count == size:
				if ll == str_list:
					t = j.next
					j.next = None
					res.append(i)
					j = t
					i = j
					count = 0
					ll = [0] * 26
				else:
					ll[ord(i.data) - ord('a')] -= 1
					i = i.next
					j = j.next
					count -= 1
			else:
				j = j.next
		return res


class Solution:

	def findAnagrams(self, head, s):
		d = {}
		for x in s:
			d[x] = d.get(x, 0) + 1
		cd = d.copy()
		output = []
		currhead = head
		while currhead != None:
			curr = currhead
			count = 0
			while curr != None:
				if cd.get(curr.data, 0) == 0:
					currhead = currhead.next
					cd = d.copy()
					count = 0
					break
				else:
					cd[curr.data] = cd[curr.data] - 1
					count += 1
				if count == len(s):
					count = 0
					cd = d.copy()
					output.append(currhead)
					currhead = curr.next
					curr.next = None
					break
				curr = curr.next
		return output