Nekomata + -1, 6 bytes

↕:∆Zƶ¿

Attempt This Online!

↕:∆Zƶ¿
↕           Find a permutation of the input
 :   ¿      Such that
  ∆         The differences between adjacent elements
   Z        Are nonzero
    ƶ       And are small (absolute values <= 1)

The -1 flag outputs the first valid solution.

Python, 102 101 100 98 bytes

lambda l:min(permutations(l),key=lambda x:{-1,1,*map(int.__sub__,x,x[1:])})
from itertools import*

Attempt This Online!

Intentionally inefficient to save characters; could not complete the final test case in any reasonable length of time (testing 51 quintillion permutations is... technically possible).

Edit 1: Since I had access to all of itertools anyway, I replaced zip(x,x[1:]) with the one character shorter (and faster to boot) pairwise(x).

Edit 2: Shaved one more by dropping pairwise, because subset testing means a single map can do the trick without relying on zip at all.

Edit 3: Shaved two more with pure evil, using the weakly ordered nature of sets and the guarantee that there will be some solution. By making the key a set with -1 and 1 already included, any passing result will have a key of {-1,1}, while non-passing solutions will have a key with at least one additional value. Thus, the passing results will be strict subsets of all non-passing results (which would be ordered with respect to each other only in the most useless ways), and min will return an arbitrary (not random, just dependent on input order) passing result.

Big thanks to Jonathan Allan for the last two improvements.

R, 117 116 111 bytes

Edit: -1 byte thanks to Glory2Ukraine.

f=\(x,y={})`if`(any(x|T),unlist(Map(\(i)f(x[-i],c(x[i],y)),which((x-c(y,NA)[1])^2==1|!any(y|T))),F)[1],list(y))

Attempt This Online!

Recursive function that returns the ordered result as a vector in a single-element list.

R has no (built-in) permutations function, so here we gradually build-up the ordered result by starting with each element of x, and trying to prepend elements with an absolute difference of 1 to the first element of the result-so-far.

Ungolfed code:

f=function(x,y={}){             # start with input x 
                                # and empty result-so-far y
    if(length(x)==0) y          # if there's no more x, return the result
    else if(length(y)==0)       # if there's no result-so-far, 
        lapply(seq(x),          #  iterate over each element of x
            function(i)f(x[-i],x[i]))
                                #  putting it into y 
                                #  & recursively calling f with x without this element
    else lapply(which(abs(x-y[1])==1),
                                #  otherwise, iterate over elements of x that 
                                #  have an absolute difference of 1 from the
                                #  first element of y
            function(i)f(x[-i],c(x[i],y)))
                                #  prepending it to y
                                # & recursively calling f with x without this element
}

R, 42 bytes

\(a){while(any(diff(a)^2-1))a=sample(a);a}

Attempt This Online!

Randomized. Shuffles the vector randomly until the condition is met. Will usually time out on large inputs.

This comes out much shorter than the deterministic R answer, which currently stands at 111 bytes.

Jelly, 8 bytes

Œ!ạƝE$ƇḢ

Try It Online!

Œ!ạƝE$ƇḢ    main link
Œ!          all permutations
      Ƈ     filter for permutations where
  ạƝ        the absolute differences of each neighboring pair
    E       are all equal
       Ḣ    take the first match

thanks to jonathan allan for this clever observation! because the list can be ordered such that the absolute differences are all \$d = 1\$, then it is impossible to order it such that the absolute differences are all some \$d \neq 1\$ (suppose it is possible; then, there must be two values \$a, b, |a - b| = 1\$, but their difference is the sum of the differences of each pair between them which is a multiple of \$d\$, which is impossible). therefore, if the absolute differences are all equal, they must all be 1

old version

Œ!I*`Ƒ$ƇḢ    main link
Œ!           all permutations
       Ƈ     filter for permutations where
  I          the difference of each neighbor
     Ƒ       is invariant when
   *`        you exponentiate each value by itself (this is only true for ±1)
        Ḣ    take the first such permutation

-1 byte by switching from ạƝ (absolute difference of each pair) to I (difference of each pair) because the *`Ƒ check (x => x == (x ** x)) works for -1 as well

Œ!ạƝỊƑ$ƇḢ also works by checking invariant under Ị ("insignificant" — absolute value less than or equal to 1). this works because any integer above 1 will return 0 for insignificant, and 0 will return 1 which is not equal, so this only works for 1

Haskell, 117 bytes

a%(b:s)|a==b=s|1<2=b:a%s;_%b=b;p[]=[[]];p x=[y:z|y<-x,z<-p$y%x];f=head.filter((all((1==).abs)).(zipWith(-)<*>tail)).p

Try it online!

Or more nicely formatted:

a%(b:s)|a==b=s|1<2=b:a%s;
_%b=b;
p[]=[[]];
p x=[y:z|y<-x,z<-p$y%x];
f=head.filter((all((1==).abs)).(zipWith(-)<*>tail)).p

This does not use functions from the Data.List library, and instead replicates them as follows:

• % is our List.delete function.
• p is our List.permutations function (with duplicates allowed).
• Finally f is main target function.

If we were to import Data.List, we could simply use List.permutations and have an 81 byte solution:

import Data.List;f=head.filter((all((1==).abs)).(zipWith(-)<*>tail)).permutations

This becomes very slow as test case length grows as we test all permutations.

Python3, 135 bytes

def f(l):
 q=[([],l)]
 for a,l in q:
  if[]==l:return a
  for i,j in enumerate(l):q+=[(a+[j],l[:i]+l[i+1:])]*([]==a or abs(a[-1]-j)==1)

Try it online!

05AB1E, 6 bytes

œ.Δ¥ÄP

Try it online or verify (almost) all test cases. (Test suit omits the last test case, which times out.)

Alternatively, outputting all valid results is 6 bytes as well:

œêʒ¥ÄP

Try it online or verify all test cases. (Test suite times out, even with the omitted large test case.)

Explanation:

œ      # Get all permutations of the (implicit) input-list
 .Δ    # Find the first that's truthy for:
   ¥   #  Get the deltas / forward-differences
    Ä  #  Get the absolute value of each
     P #  Take the product
       #  (note, only 1 is truthy in 05AB1E)
       # (after which the found result is output implicitly)

 ê     # Sort and uniquify this list of permutations
  ʒ    # Filter this list of lists by:
       #  ...
       # (after which all found results are output implicitly)

Google Sheets, 152 bytes

=let(a,tocol(A:A,1),r,rows(a),i,sequence(r),f,lambda(f,a,if(1=r-sum(sort(n(1=abs(filter(a,i<r)-filter(a,i>1))))),a,f(f,sort(a,randarray(r),1)))),f(f,a))

Non-deterministic. Tends to run into the recursion limit with lists of more than eight integers.

Prettified:

=let(
  a, tocol(A:A, 1),
  r, rows(a),
  i, sequence(r),
  f, lambda(f, a, if(
    1 = r - sum(sort(n(1 = abs(filter(a, i < r) - filter(a, i > 1))))),
    a, 
    f(f, sort(a, randarray(r), 1))
  )),
  f(f, a)
)

Vyxal 3, 7 bytes

⧖ʎδ⦷1≊⎋

Vyxal It Online!

⧖ʎδ⦷1≊⎋­⁡​‎‎⁡⁠⁢��‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠⁠‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌­
 ʎ       # ‎⁡filter...
⧖        # ‎⁢permutations of the input by...
  δ      # ‎⁣are the delta's
   ⦷     # ‎⁤absolute values
    1≊   # ‎⁢⁡all equal to 1?
      ⎋  # ‎⁢⁢close the filter and get head
💎

Created with the help of Luminespire.

<script type="vyxal3">
⧖ʎδ⦷1≊⎋
</script>
<script>
    args=[["[1,2]"],["[4, 5, 5, 5, 4]"],["[1, 3, 2, 4, 5]"],["[3, 0, 1, 1, 2, 4]"],["[4, 2, 3, 4, 4, 5, 5]"],["[1, 7, 5, 2, 6, 4, 4, 3, 3]"]]
</script>
<script src="https://themoonisacheese.github.io/snippeterpreter/snippet.js" type="module"/>

Japt -g, 9 bytes

á kÈäa dÉ

Try it

á kÈäa dÉ     :Implicit input of array
á             :Permutations
  k           :Remove elements that return true
   È          :When passed through the following function
    ä         :  Consecutive pairs
     a        :    Reduced by absolute difference
       d      :  Any truthy (not 0)
        É     :    Subtract 1
              :Implicit output of first element

Charcoal, 37 bytes

⊞υ⟦⟧ＦυＦθＦ∧¬∧ι⊖↔⁻↨ι⁰κ›№θκ№ικ⊞υ⁺ι⟦κ⟧Ｉ⊟υ

Try it online! Link is to verbose version of code. Explanation: Finds all paths in the undirected graph and outputs the last one found which will always be the longest and therefore a solution (assuming one exists).

⊞υ⟦⟧Ｆυ

Start a depth-first search with a path with no nodes.

Ｆθ

Loop over each potential node.

Ｆ∧¬∧ι⊖↔⁻↨ι⁰κ›№θκ№ικ

If this node is adjacent and it has not already been exhausted, then...

⊞υ⁺ι⟦κ⟧

... add a new path to the search list that includes this node.

Ｉ⊟υ

Output the last path found.

APL+WIN, 47 bytes

Prompts for vector of integers. Times out for last test case.

s←⎕⋄:while (¯1+⍴s)≠+/1=|-2-/s←s[(⍴s)?⍴s]⋄:end⋄s

Try it online! Thanks to Dyalog Classic APL

JavaScript (ES7), 77 bytes

f=o=(a,...b)=>a.map((v,i)=>(v-b[0])**2-1||f(a.filter(_=>i--),v,...b))+a?o:o=b

Try it online!

Commented

f =             // f is a recursive function
o =             // o is the output
(a, ...b) =>    // a[] = input array, b[] = current permutation
a.map((v, i) => // for each value v at index i in a[]:
  (v - b[0])    //   if the squared difference between v and b[0]
  ** 2 - 1 ||   //   is equal to 1:
  f(            //     do a recursive call:
    a.filter(   //       pass a copy of a[]
      _ => i--  //       without the i-th element
    ),          //
    v,          //       prepend v
    ...b        //       to b[]
  )             //     end of recursive call
)               // end of map()
+ a ?           // if a[] was not empty:
  o             //   return o[]
:               // else:
  o = b         //   we have a valid permutation: copy b[] to o[]

JavaScript (ES7), 65 bytes

Non-deterministic version. Likely to stack-overflow on large inputs (except maybe on Safari, as pointed out by Themoonisacheese).

f=a=>a.some(p=v=>(p-(p=v))**2-1)?f(a.sort(_=>Math.random()-.5)):a

Try it online!

Commented

f = a =>            // f is a recursive function taking a[]
a.some(p =          // p = previous value, initially NaN'ish
  v =>              // for each value v in a[]:
  (p - (p = v))     //   test if the squared difference between
  ** 2 - 1          //   p and v is not 1, and update p to v
)                   // end of some()
?                   // if truthy:
  f(                //   do a recursive call:
    a.sort(_ =>     //     with a[] shuffled
      Math.random() //     using a sort with random numbers
      - .5          //     in [-0.5 .. 0.5[
    )               //     (this produces a biased permutation,
                    //     but we don't care)
  )                 //   end of recursive call
:                   // else:
  a                 //   success: return a[]

Haskell + hgl, 17 bytes

g1(mF eq1<δ')<pm

Explanation

• pm get all permutations
• g1 get the frist one such that ...
• δ' the absolute difference of consecutive elements
• mF are all
• eq1 equal to 1

Reflection

• I would like a "permutations such that ..." function. It probably wouldn't save bytes here but would save bytes if the challenge were "output all solutions" rather than "output one solution".
• I thought there was a built in for determining if all the elements of a list were equal to some value, but I can't find it. I should look a little harder and if I don't find it implement it.

Husk, 7 bytes

ḟoËaẊ-P

Try it online!

ḟoËaẊ-P     # 
ḟ           # Return first value that gives truthy result of
 o          #  function composition: (o f g) x means f (g x)
  Ë         #   Are function results all equal?
   a        #    function = absolute value
    Ẋ       #   Map over pairs of adjacent values
     -      #    subtract
            # applied to 
      P     # List of all permutations of the input

Maple, 67 bytes

s->select(q->{abs~(q[..-2]-q[2..])[]}={1},combinat:-permute(s))[1];

Checks all permutations for absolute differences = 1.

APL(NARS), 64 chars

f←{(a b)←⍵⋄a≡⍬:b⋄{(b≡⍬)∨1=∣⍵-↑b:f(a∼⍦⍵)(⍵,b)⋄⍬}¨a}⋄h←{(≢⍵)↑∊f⍵⍬}

Interpreter: NARS2000 (Win32) Version # 0.5.14.11

That would be a try to port in APL the recursive Arnauld JavaScript answer. They are 2 function h and f.

It seems that is possible eliminate from array possible solutions all the zilde (that means fail) with ∊ and know the length of the solution, that is the length of input say it n, get the first n elements in the array ∊solutions, these n elements array will be the solution returned.

test:

  )box on
Already ON
  h 1 2
┌2───┐
│ 2 1│
└~───┘
  h 4 5 5 5 4
┌5─────────┐
│ 5 4 5 4 5│
└~─────────┘
  h 1 7 5 2 6 4 4 3 3
┌9─────────────────┐
│ 7 6 5 4 3 4 3 2 1│
└~─────────────────┘
  h 6 10 2 12 13 5 7 1 14 9 2 1 4 10 13 11 11 12 8 3 9
┌21─────────────────────────────────────────────────┐
│ 1 2 1 2 3 4 5 6 7 8 9 10 9 10 11 12 11 12 13 14 13│
└~──────────────────────────────────────────────────┘
 2{∣⍵-⍺}/h 6 10 2 12 13 5 7 1 14 9 2 1 4 10 13 11 11 12 8 3 9
┌20──────────────────────────────────────┐
│ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1│
└~───────────────────────────────────────┘

if not exist one solution it seems h return for input array of n elements, one array of n zeros

  h 1 2 9
┌3─────┐
│ 0 0 0│
└~─────┘

but this can not happen reading the question.

APL(NARS), 118 chars

q←{⍵≡⍬:⍺⋄⍬≡m←∪⍵/⍨1=∣⍵-⍺[≢⍺]:⍬⋄⍬≢r←(⍺,c)∇⍵∼⍦c←↑m:r⋄⍬≡m←m∼c:⍬⋄(⍺,c)∇⍵∼⍦c←↑m}    
g←{k←⍵⋄{⍵>≢k:⍬⋄⍬≡v←j q k∼⍦j←,k[⍵]:∇⍵+1⋄v}1}

// 75+43=118

Interpreter: NARS2000 (Win32) Version # 0.5.14.11

g function has as input one array of integers, of at last two elements, and would return zilde, the void numeric list, if there is no permutation of the elements of input array such that the difference each contiguous elements of the array result is 1, else it would return one permutation of elements of input array such that the difference each contiguous elements of the array result 1.

q function is based on observation that if C is a list of integers and y is a integer, the set

{x is in ∪C: 1=|x-y|} 

(where ∪C is the list of element of C without repetitions) can have only 0 or 1 or 2 elements, and the function q search in the deep (in the case 1 or 2 elements, in the way in case 2 elements if first find one solution in the max deep, it is returned and the second element is not used in the successive recursive call) the first solution. Furthermore it would be not necessary q search all repeated elements, but just one, because the answer that q would obtain would be the same (it is for that it was used ∪ in ∪⍵/⍨1=∣⍵-⍺[≢⍺])

test:

  q←{⍵≡⍬:⍺⋄⍬≡m←∪⍵/⍨1=∣⍵-⍺[≢⍺]:⍬⋄⍬≢r←(⍺,c)∇⍵∼⍦c←↑m:r⋄⍬≡m←m∼c:⍬⋄(⍺,c)∇⍵∼⍦c←↑m}    
  g←{k←⍵⋄{⍵>≢k:⍬⋄⍬≡v←j q k∼⍦j←,k[⍵]:∇⍵+1⋄v}1}
  g 6 10 2 12 13 5 7 1 14 9 2 1 4 10 13 11 11 12 8 3 9
┌21─────────────────────────────────────────────────┐
│ 13 14 13 12 11 12 11 10 9 10 9 8 7 6 5 4 3 2 1 2 1│
└~──────────────────────────────────────────────────┘

note that "g 6 10 2 12 13 5 7 1 14 9 2 1 4 10 13 11 11 12 8 3 9" is executed here in 330ms where "h 6 10 2 12 13 5 7 1 14 9 2 1 4 10 13 11 11 12 8 3 9" is executed in 40s at last 40x more... so it is possible find

  g 6 10 2 12 13 5 7 16 1 14 3 9 2 1 15 4 10 2 13 11 11 12 8 3 9 0 1 8 14 9 2 15
┌32───────────────────────────────────────────────────────────────────────────┐
│ 2 1 2 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 15 14 13 12 11 10 9 8 9│
└~────────────────────────────────────────────────────────────────────────────┘

in less of 1 second

  2{∣⍵-⍺}/g 6 10 2 12 13 5 7 16 1 14 3 9 2 1 15 4 10 2 13 11 11 12 8 3 9 0 1 8 14 9 2 15
┌31────────────────────────────────────────────────────────────┐
│ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1│
└~─────────────────────────────────────────────────────────────┘

reduction of paths it seems okay as speed not as chars length.