Merge pairs on common integer with restrictions

The code below works as follows:

1. Create a new list with size of old list + 1 (The maximum size theoutput can reach).
2. Start with the first pair in your list of pairs with its first valueat the end of your new list, and its second value at the start ofyour new list. And mark them as visited using a python dictionaryfor example.
3. Maintain two indexes of your first and last positions pointing tothe end and start of your new list respectively initially.
4. Iterate on the rest of pairs, if for pair i its both values exist ordon't exist in the dictionary, skip it. Else, merge the not visitedvalue to element at the first index or the last index (depending onthe position of the visited value), and update your index. Note thatno merging will happen if the visited value is not at the first orthe last index (if it is somewhere in the middle).
5. Return a concatenation of new list[first index to end] with newlist[start to the last index].

Note: every merging operation takes O(1). Also you can use an array of booleans instead of dictionary if you know the range of pairs values.

#The function takes a list of pairs as an argumentdef merge_lst(lst):  #Dictionary to check if value is already in array  visited = dict()  #Length of old list  lst_len = len(lst)  #New list will have at most lst_len+1 elements  new_lst = [0]*(lst_len+1)  #Put the first pair values in last and first elements of the new list repectively and mark them as visited  new_lst[lst_len], new_lst[0] = lst[0][0], lst[0][1]  visited[lst[0][0]], visited[lst[0][1]] = True, True  #Maintain the positions of your first and last elements, which are the the last index and 0 respectively now  first_index, last_index = lst_len, 0  #Iterate on the rest of pairs  for i in range(1, lst_len):    #Check if pair[a, b] are already visited    a_exists, b_exists = lst[i][0] in visited, lst[i][1] in visited    #Skip if they both exist or don't exist    if(a_exists == b_exists):      continue    #Assume a was the common one    common, to_merge = lst[i][0], lst[i][1]    #If b exists (b is the common not a), then just swap    if(b_exists):      common, to_merge = lst[i][1], lst[i][0]    #If the common element is at the first index, the first element and index are updated    if(new_lst[first_index] == common):      first_index-=1      new_lst[first_index] = to_merge      visited[to_merge] = True    #If the common element is at the last index, the last element and index are updated    elif(new_lst[last_index] == common):      last_index+=1      new_lst[last_index] = to_merge      visited[to_merge] = True    #Else, the common element is somewhre in the middle (already connected)  #Return concatenation of new_lst[first_index to the end] with new_lst[0 to the last_index]   return new_lst[first_index:lst_len+1]+new_lst[0:last_index+1]

This code gives correct output for all of your mentioned test cases.