присоединиться списки на основе общей головы или хвоста

Question

Какой самый быстрый способ решить следующую я буду объединять несколько списков на основе общей головы или хвоста

input = ([5,6,7], [1,2,3], [3,4,5], [8, 9]) 
output = [1, 2, 3, 4, 5, 6, 7] 

Answer 1

>>> def chain(inp): 
    d = {} 
    for i in inp: 
     d[i[0]] = i[:], i[-1] 
    l, n = d.pop(min(d)) 
    while True: 
     lt, n = d.pop(n, [None, None]) 
     if n is None: 
      if len(d) == len(inp) - 1: 
       l, n = d.pop(min(d)) 
       continue 
      break 
     l += lt[1:] 
    return l 

>>> chain(input) 
[1, 2, 3, 4, 5, 6, 7] 
>>> chain(([5,6,7], [1,2,10], [3,4,5], [8, 9])) 
[3, 4, 5, 6, 7]