#!/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( defined( my $place = first {
      $_ == 0 ? $in[$in] ne $out[0] : # at start?
      $_ == @out ? $in[$in] ne $out[-1] : # at end?
      $out[$_-1] ne $in[$in] && $out[$_] ne $in[$in] # in middle?
      } 0 .. @out ) )
      {
      splice @out, $place, 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