join lists based on common head or tail

Question

What is the fastest way to solve the following I will to join several lists based on common head or tail

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]