#!/usr/bin/perl

use strict; # https://www.perlmonks.org/?node_id=11154597
use warnings;

use List::AllUtils qw( first shuffle );
my @in = shuffle <DATA>;
my @out = shift @in;

LOOP:
while( @in )
  {
  for my $in ( 0 .. $#in )
    {
    if( $in[$in] ne $out[0] ) # put at start
      {
      unshift @out, splice @in, $in, 1;
      next LOOP;
      }
    elsif( $in[$in] ne $out[-1] ) # put at end
      {
      push @out, splice @in, $in, 1;
      next LOOP;
      }
    else # put in first middle place it fits
      {
      if( my $pick = first {
        $out[$_ - 1] ne $in[$in] and $out[$_] ne $in[$in] } 1 .. $#out )
        {
        splice @out, $pick, 0, splice @in, $in, 1;
        next LOOP;
        }
      }
    }
  die "FAILED\nin\n @in\nout\n @out";
  }
print @out;

__DATA__
Line 1
Line 2
Line 3
Line 3
Line 3
Line 4
Line 8