Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Streitig ist, ob die La Suisse Versicherungen den Versicherungsfall zu Recht per 1. Juni 1998 abgeschlossen und weitere Leistungen mit der Begründung abgelehnt hat, dass keine Unfallfolgen mehr vorlägen. Dabei ist auf den Sachverhalt abzustellen, wie er zur Zeit des Einspracheentscheides gegeben war (<ref-ruling> Erw. 1b mit Hinweis).
2.- a) Die Leistungspflicht eines Unfallversicherers gemäss UVG setzt zunächst voraus, dass zwischen dem Unfallereignis und dem eingetretenen Schaden (Krankheit, Invalidität, Tod) ein natürlicher Kausalzusammenhang besteht. Ursachen im Sinne des natürlichen Kausalzusammenhangs sind alle Umstände, ohne deren Vorhandensein der eingetretene Erfolg nicht als eingetreten oder nicht als in der gleichen Weise bzw. nicht zur gleichen Zeit eingetreten gedacht werden kann. Entsprechend dieser Umschreibung ist für die Bejahung des natürlichen Kausalzusammenhangs nicht erforderlich, dass ein Unfall die alleinige oder unmittelbare Ursache gesundheitlicher Störungen ist; es genügt, dass das schädigende Ereignis zusammen mit anderen Bedingungen die körperliche oder geistige Integrität der versicherten Person beeinträchtigt hat, der Unfall mit andern Worten nicht weggedacht werden kann, ohne dass auch die eingetretene gesundheitliche Störung entfiele (<ref-ruling> Erw. 1, 118 V 289 Erw. 1b, je mit Hinweisen).
Ob zwischen einem schädigenden Ereignis und einer gesundheitlichen Störung ein natürlicher Kausalzusammenhang besteht, ist eine Tatfrage, worüber die Verwaltung bzw. im Beschwerdefall das Gericht im Rahmen der ihm obliegenden Beweiswürdigung nach dem im Sozialversicherungsrecht üblichen Beweisgrad der überwiegenden Wahrscheinlichkeit zu befinden hat. Die blosse Möglichkeit eines Zusammenhangs genügt für die Begründung eines Leistungsanspruches nicht (<ref-ruling> Erw. 1, 118 V 289 Erw. 1b, je mit Hinweisen).
b) Ist die Unfallkausalität einmal mit der erforderlichen Wahrscheinlichkeit nachgewiesen, entfällt die deswegen anerkannte Leistungspflicht des Unfallversicherers erst, wenn der Unfall nach einiger Zeit überhaupt keine natürliche Ursache des Gesundheitsschadens mehr darstellt, wenn also Letzterer nur noch und ausschliesslich vom unfallfremden Faktor beherrscht wird (Maurer, Schweizerisches Unfallversicherungsrecht, Bern 1985, S. 474). Dies trifft dann zu, wenn - nach vorübergehender Verschlimmerung oder erstmaliger Manifestierung des krankhaften Vorzustandes - entweder der Gesundheitszustand, wie er unmittelbar vor dem Unfall bestanden hat (status quo ante), oder aber derjenige Zustand, wie er sich nach dem schicksalsmässigen Verlauf auch ohne Unfall früher oder später eingestellt hätte (status quo sine) erreicht ist (Morger, Zusammentreffen verschiedener Schadensursachen [<ref-law>] in: Versicherungskurier 42/1987 S. 133). Ebenso wie der leistungsbegründende natürliche Kausalzusammenhang muss das Dahinfallen jeder kausalen Bedeutung von unfallbedingten Ursachen eines Gesundheitsschadens mit dem im Sozialversicherungsrecht allgemein üblichen Beweisgrad der überwiegenden Wahrscheinlichkeit nachgewiesen sein. Die blosse Möglichkeit nunmehr gänzlich fehlender ursächlicher Auswirkungen des Unfalles genügt nicht (<ref-ruling> Erw. 4a und 376 Erw. 3a, 115 V 142 Erw. 8b mit Hinweisen). Da es sich hierbei um eine anspruchsaufhebende Tatfrage handelt, liegt die entsprechende Beweislast - anders als bei der Frage, ob ein leistungsbegründender natürlicher Kausalzusammenhang gegeben ist - nicht bei der versicherten Person, sondern beim Unfallversicherer (RKUV 1994 Nr. U 206 S. 329 Erw. 3b, 1992 Nr. U 142 S. 76 Erw. 4b).
3.- a) Nach den Angaben des wegen Schwindels, Kopf- und Nackenschmerzen aufgesuchten Hausarztes Dr. S._ hat der Beschwerdegegner beim Unfall ein massives HWSSchleudertrauma mit erheblicher Beeinträchtigung der HWSBeweglichkeit, jedoch ohne knöcherne Läsion erlitten (Berichte vom 22. Dezember 1997 und 15. Februar 1998). Die gleiche Diagnose findet sich in der Stellungnahme des Neurologen Dr. H._ vom 19. November 1997. Dieser untersuchte zudem, ob die rund eine Woche nach dem Unfall erstmals aufgetretenen Dysästhesien und Hypästhesie im ulnaren Hand- und Unterarmabschnitt allenfalls mit der bereits vorbestehenden Bandscheibenprotrusion mediolateral rechts C6/C7 oder einer anderen unfallfremden Ursache in Verbindung gebracht werden könnte, und verneinte dies. Besondere neurologische Auffälligkeiten konnte er nicht feststellen. Am 7. September 1998 wies Dr. S._ in einem Schreiben an die Fortuna Lebens-Versicherungs-Gesellschaft auf den schleppenden Heilungsverlauf hin. Neben der nach wie vor deutlichen schmerzhaften Einschränkung der Beweglichkeit der HWS mit ausstrahlenden Kribbelparästhesien in die Arme verwies er zudem auf eine Störung der psychischen Befindlichkeit mit Antriebsschwäche, Konzentrationsstörungen und verminderter Gedächtnisleistung. Dies wird im Wesentlichen im Austrittsbericht der Rheuma- und Rehabilitationsklinik Y._ vom 17. Februar 1999, wo der Versicherte vom 12. Januar bis 9. Februar 1999 stationär in Behandlung stand, bestätigt. Darin wird das gesamte Beschwerdebild indessen als persistierendes zervikovertebrales und zervikozephales Schmerzsyndrom nach der HWSDistorsion vom 31. Oktober 1997 bezeichnet. Auch wird der Verdacht eines zervikoradikulären Syndroms C7 bei rechtslateralem, auch infraforaminal gelegenem Diskusprolaps C6/C7 und nadelmyographischer Veränderung im Bereich des Musculus triceps geäussert. Eine eigentliche Instabilität der HWS konnte nicht festgestellt werden. Dagegen wird in diesem Bericht angesichts der festgestelltermassen starken Diskrepanz zwischen dem Selbsterleben des Versicherten und der ärztlichen Einschätzung der Leistungsfähigkeit auf eine ausgeprägte psychische Fixierung auf die Symptomatik erkannt, welche im Falle deutlich überdurchschnittlicher prämorbider kognitiver Fähigkeiten durchaus denkbar sei und einen entsprechenden Anpassungsprozess des Patienten erfordere. Es wird eine psychologische Unterstützung zum Erlernen von Schmerz-Copingstrategien empfohlen. Seit dem 15. März 1999 absolviert der Beschwerdegegner denn auch bei Dr. E._ eine Psychotherapie. Der von der La Suisse Versicherungen beauftragte Dr. A._ erachtet im Bericht vom 9. Juli 1999 die bereits vor dem Unfall vorhanden gewesene degenerative Veränderung des Segments C6/C7 als zumindest mitursächlich für die andauernden Beschwerden, wobei er es als am wahrscheinlichsten bezeichnet, dass durch das Ereignis eine bis dahin klinisch stumme Diskopathie C6/C7 zu einer seither zunehmenden symptomatischen Protrusion/Diskushernie C6/C7 werden konnte; weitere unfallfremde Faktoren wie die prämorbide Persönlichkeit des Beschwerdegegners sowie berufliche Probleme hätten die Beschwerden zusätzlich überlagert. Frau Dr. W._ erhebt im für die Rehaklinik Z._ am 28. September 1999 im Anschluss an den Klinikaufenthalt vom 10. August bis 7. September 1999 verfassten Gutachten einen Status nach HWS-Distorsionstrauma mit persistierendem zervikozephalem Syndrom, intermittierendem zervikothorakalem Syndrom, neuropsychologischen Defiziten sowie depressiven Episoden.
b) Wie von der Vorinstanz zutreffend festgehalten, ist bei diagnostiziertem Schleudertrauma der HWS der natürliche Kausalzusammenhang zwischen Unfall und Arbeits- oder Erwerbsunfähigkeit in der Regel zu bejahen, wenn ein für diese Verletzung typisches Beschwerdebild mit einer Häufung von Beschwerden wie diffuse Kopfschmerzen, Schwindel, Konzentrations- und Gedächtnisstörungen, Übelkeit, rasche Ermüdbarkeit, Visusstörungen, Reizbarkeit, Affektlabilität, Depression, Wesensveränderungen usw. vorliegt (<ref-ruling> Erw. 4b). In <ref-ruling> hat das Eidgenössische Versicherungsgericht festgehalten, aus <ref-ruling> dürfe nicht geschlossen werden, dass bei der Beurteilung der natürlichen Kausalität von Folgeschäden nach Verletzungen der HWS der natürliche Kausalzusammenhang ungeachtet der medizinischen Untersuchungsergebnisse gleichsam als von vornherein gegeben vorausgesetzt werde (<ref-ruling> Erw. 2b/aa). Präzisierend führte es weiter aus, zur Bejahung der Frage, ob ein natürlicher Kausalzusammenhang zwischen einer Schleuderverletzung der HWS ohne organisch nachweisbare Beschwerden und den eingetretenen Gesundheitsschädigungen besteht, müssten die geklagten Beschwerden medizinisch einer fassbaren gesundheitlichen Beeinträchtigung zugeschrieben werden können und die Gesundheitsschädigung mit dem im Sozialversicherungsrecht allgemein erforderlichen Beweisgrad der überwiegenden Wahrscheinlichkeit in einem ursächlichen Zusammenhang mit dem versicherten Unfall stehen (<ref-ruling> f. Erw. 2b/bb). Die Tatsache, dass der im Zusammenhang mit einer HWS-Verletzung sich manifestierende Beschwerdekomplex mitunter noch andere Ursachen haben kann, darf nicht von vornherein zur Verneinung der natürlichen Kausalität führen, da der Unfall als eine Teilursache für die Bejahung des natürlichen Kausalzusammenhangs genügt (<ref-ruling> Erw. 1 in fine mit Hinweis). Nach heutiger medizinischer Erkenntnis können bei einem Schleudertrauma der HWS auch ohne nachweisbare pathologische Befunde noch Jahre nach dem Unfall funktionelle Ausfälle der verschiedensten Art auftreten (<ref-ruling> Erw. 5d/aa).
c) Wenn die Vorinstanz im Lichte dieser Rechtsprechung zum Schluss gelangt ist, dass die vom Versicherten geklagten Beschwerden zumindest teilweise in einem natürlichen Kausalzusammenhang mit dem Unfall vom 31. Oktober 1997 stehen, so lässt sich dies nicht beanstanden. Zum einen steht auf Grund der zahlreichen, im Wesentlichen übereinstimmenden ärztlichen Berichte fest, dass der Versicherte ein massives HWS-Distorsionstrauma im Sinne eines so genannten Schleudertraumas erlitten hat; zum andern klagt er glaubhaft über Beschwerden, die zum typischen Beschwerdebild eines Schleudertraumas gehören. So hat er schon wenige Stunden nach dem Unfall über Kopfschmerzen und Schwindel, später auch über Gedächtnis- und Konzentrationsstörungen, rasche Ermüdbarkeit, Übelkeit und schliesslich auch Depressionen geklagt. Diese Störungen haben zu einer Beeinträchtigung der Arbeits- bzw. Erwerbsfähigkeit geführt, welche über den Tag des Einspracheentscheides hinaus angedauert hat. Inwieweit dabei auch die vorbestandene degenerative Veränderung der HWS im Bereich C6/C7 ebenfalls dazu beigetragen hat, ist unerheblich, solange nach den medizinischen Akten anzunehmen ist, dass der Unfall zumindest eine Teilursache der Gesundheitsschädigung bildet. Dass zum Zeitpunkt des Einspracheentscheides der status quo sine erreicht worden ist, wovon die Beschwerdeführerin auszugehen scheint, lässt sich dagegen anhand der Arztberichte nicht mit überwiegender Wahrscheinlichkeit sagen (vgl. Erw. 2b hievor).
4.- a) Die Leistungspflicht des Unfallversicherers setzt im Weiteren voraus, dass zwischen dem Unfallereignis und dem eingetretenen Schaden ein adäquater Kausalzusammenhang besteht. Nach der Rechtsprechung hat ein Ereignis dann als adäquate Ursache eines Erfolges zu gelten, wenn es nach dem gewöhnlichen Lauf der Dinge und nach der allgemeinen Lebenserfahrung an sich geeignet ist, einen Erfolg von der Art des eingetretenen herbeizuführen, der Eintritt dieses Erfolges also durch das Ereignis allgemein als begünstigt erscheint (<ref-ruling> Erw. 3a, 123 V 103 Erw. 3d, 139 Erw. 3c, 122 V 416 Erw. 2a, 121 V 49 Erw. 3a mit Hinweisen).
Nach der mit <ref-ruling> geänderten Rechtsprechung zum adäquaten Kausalzusammenhang zwischen Unfällen mit Schleudertrauma der HWS ohne organisch nachweisbare Funktionsausfälle und anhaltenden Beschwerden mit Auswirkungen auf die Arbeits- und Erwerbsfähigkeit ist in analoger Anwendung der Rechtsprechung zu den psychischen Unfallfolgen (<ref-ruling> Erw. 6) für die Bejahung des adäquaten Kausalzusammenhangs im Einzelfall zu verlangen, dass dem Unfall für die Entstehung der Arbeits- bzw. Erwerbsunfähigkeit eine massgebende Bedeutung zukommt. Dies trifft dann zu, wenn er objektiv eine gewisse Schwere aufweist oder mit andern Worten ernsthaft ins Gewicht fällt. Für die Beurteilung dieser Frage ist gemäss <ref-ruling> Erw. 6 an das Unfallereignis anzuknüpfen, wobei - ausgehend vom augenfälligen Geschehensablauf - folgende Einteilung vorgenommen wurde: banale bzw. leichte Unfälle einerseits, schwere Unfälle anderseits und schliesslich der dazwischen liegende mittlere Bereich. Während bei leichten Unfällen der adäquate Kausalzusammenhang in der Regel ohne weiteres verneint werden kann, weil auf Grund der allgemeinen Lebenserfahrung, aber auch unter Einbezug unfallmedizinischer Erkenntnisse davon ausgegangen werden darf, dass ein solcher Unfall nicht geeignet ist, einen erheblichen Gesundheitsschaden zu verursachen, ist der adäquate Kausalzusammenhang zwischen Unfall und Folgen bei schweren Unfällen in der Regel zu bejahen. Denn nach dem gewöhnlichen Lauf der Dinge und nach der allgemeinen Lebenserfahrung sind solche Unfälle geeignet, entsprechende Gesundheitsschäden zu bewirken. Bei Unfällen aus dem mittleren Bereich lässt sich die Frage, ob zwischen Unfall und Folgen ein adäquater Kausalzusammenhang besteht, nicht auf Grund des Unfalles allein schlüssig beantworten. Es sind daher weitere, objektiv erfassbare Umstände, welche unmittelbar mit dem Unfall im Zusammenhang stehen oder als direkte bzw. indirekte Folgen davon erscheinen, in eine Gesamtwürdigung einzubeziehen. Als wichtigste Kriterien sind im Zusammenhang mit dem Schleudertrauma der HWS zu nennen:
- besonders dramatische Begleitumstände oder besondere
Eindrücklichkeit des Unfalls;
- die Schwere oder besondere Art der erlittenen Verletzun-
gen;
- ungewöhnlich lange Dauer der ärztlichen Behandlung;
- Dauerbeschwerden;
- ärztliche Fehlbehandlung, welche die Unfallfolgen erheb-
lich verschlimmert;
- schwieriger Heilungsverlauf und erhebliche Komplikatio-
nen; - Grad und Dauer der Arbeitsunfähigkeit.
Im Gegensatz zu den bei psychischen Fehlentwicklungen relevanten Kriterien gemäss <ref-ruling> Erw. 6c/aa wird für die Beurteilung des adäquaten Kausalzusammenhangs zwischen einem Unfall mit Schleudertrauma der HWS und in der Folge eingetretenen Beschwerden auf eine Differenzierung zwischen physischen und psychischen Komponenten verzichtet, weil es hier nicht entscheidend ist, ob Beschwerden medizinisch eher als organischer und/oder psychischer Natur bezeichnet werden. Dies gilt indessen nur solange, als dass die zum typischen Beschwerdebild eines Schleudertraumas der HWS gehörenden Beeinträchtigungen im Vergleich zu einer ausgeprägten psychischen Problematik nicht ganz in den Hintergrund treten: Andernfalls ist die Adäquanzbeurteilung unter dem Gesichtspunkt einer psychischen Fehlentwicklung nach Unfall vorzunehmen (<ref-ruling> Erw. 2a).
Der Einbezug sämtlicher objektiver Kriterien in die Gesamtwürdigung ist nicht in jedem Fall erforderlich. Je nach den konkreten Umständen kann für die Beurteilung des adäquaten Kausalzusammenhangs ein einziges Kriterium genügen. Dies trifft einerseits dann zu, wenn es sich um einen Unfall handelt, welcher zu den schwereren Fällen im mittleren Bereich zu zählen oder sogar als Grenzfall zu einem schweren Unfall zu qualifizieren ist. Anderseits kann im gesamten mittleren Bereich ein einziges Kriterium genügen, wenn es in besonders ausgeprägter Weise erfüllt ist. Kommt keinem Einzelkriterium besonderes bzw. ausschlaggebendes Gewicht zu, so müssen mehrere unfallbezogene Kriterien herangezogen werden. Handelt es sich beispielsweise um einen Unfall im mittleren Bereich, der aber dem Grenzbereich zu den leichten Unfällen zuzuordnen ist, müssen die weiteren zu berücksichtigenden Kriterien in gehäufter oder auffallender Weise erfüllt sein, damit die Adäquanz bejaht wird. Diese Würdigung des Unfalles zusammen mit den objektiven Kriterien führt zur Bejahung oder Verneinung des adäquaten Kausalzusammenhanges. Damit entfällt die Notwendigkeit, nach andern Ursachen zu forschen, welche möglicherweise die nach einem Schleudertrauma der HWS aufgetretenen Beschwerden mitbegünstigt haben könnten (<ref-ruling> ff. Erw. 6).
b) Ausgehend vom augenfälligen Geschehensablauf ist der Verkehrsunfall vom 31. Oktober 1997 mit der Vorinstanz und dem Versicherten dem mittleren Bereich zuzuordnen. Allein schon die Höhe des Sachschadens am Fahrzeug des Beschwerdegegners, welcher gemäss letztinstanzlich ins Recht gelegter Rechnung der Reparaturwerkstätte an die Fahrzeugversicherung vom 6. Februar 1998 rund Fr. 5500.- beträgt, schliesst die Annahme eines leichten Unfalles aus, was von der Beschwerdeführerin indessen gefordert wird.
Zwar weist das Beschwerdebild des Versicherten zum
Zeitpunkt des Einspracheentscheides (21. Mai 1999) auch eine psychische Komponente auf. Diese äussert sich in Form von depressiven Episoden, welche die Verarbeitung des Schmerzbildes erschweren. Von einer beherrschenden Dominanz der psychischen Probleme über die seit dem Unfall bestehenden Kopf- und Nackenschmerzen, die Kribbelparästhesien, die Konzentrationsstörungen, den Schwindel, die Gedächtnisstörungen und die rasche Ermüdung bei Anstrengungen zum hier interessierenden Zeitpunkt (vgl. Erw. 1) kann indessen nicht gesprochen werden. Infolgedessen ist bei der Prüfung der in Erw. 4a genannten Kriterien entgegen der in der Verwaltungsgerichtsbeschwerde vertretenen Auffassung auf eine Differenzierung zwischen physischen und psychischen Komponenten und deren Auswirkungen auf die Arbeits- bzw. Erwerbsfähigkeit zu verzichten.
Der Unfall ereignete sich weder unter besonders dramatischen Begleitumständen noch ist er als besonders eindrücklich zu bezeichnen. Ebenso wenig kann von einer ärztlichen Fehlbehandlung, welche die Unfallfolgen erheblich verschlimmerte, gesprochen werden. Zwischen dem Unfall und dem Einspracheentscheid liegen aber immerhin schon 1 1/2 Jahre. Während dieser Zeit litt der Versicherte trotz zahlreicher Therapien andauernd an einer Häufung verschiedener, für das Schleudertrauma der HWS typischen Schmerzen und war mit Ausnahme eines kurzen Unterbruchs vom 17. Februar bis längstens 16. April 1999 (Austrittsbericht der Rheuma- und Rehabilitationsklinik Y._ vom 17. Februar 1999; Zeugnis von Dr. E._ vom 16. April 1999) stets vollständig arbeitsunfähig. Weil die Arbeitsunfähigkeit weiterhin andauert und die Behandlung der permanent vorhandenen Beschwerden noch nicht abgeschlossen ist, sind die weiteren Kriterien als erfüllt zu betrachten (vgl. <ref-ruling> Erw. 7b, 2. Absatz).
Da die massgebenden unfallbezogenen Merkmale in gehäufter Weise vorliegen, ist die Adäquanz des Kausalzusammenhangs zwischen dem Unfall und den zum Zeitpunkt des Einspracheentscheids vorhandenen Beschwerden mit Auswirkungen auf die Arbeits- und Erwerbsfähigkeit zu bejahen. Hieran ändert nichts, dass der Beschwerdegegner gemäss ärztlichen Feststellungen prätraumatisch eine auffällige Persönlichkeitsstruktur mit Neigung zu psychosomatischen Reaktionen (prämorbide Persönlichkeit) aufweist. Denn für die Frage, ob ein Unfall nach dem gewöhnlichen Lauf der Dinge und der allgemeinen Lebenserfahrung geeignet sei, eine (psychische) Gesundheitsschädigung herbeizuführen, ist auf eine weite Bandbreite der Versicherten abzustellen. Hiezu gehören auch jene Versicherten, die auf Grund ihrer Veranlagung für psychische Störungen anfälliger sind und einen Unfall seelisch weniger gut verkraften als Gesunde. Im Rahmen der erwähnten weiten Bandbreite bilden auch solche Versicherte Bezugspersonen für die Adäquanzbeurteilung, welche, wie der Beschwerdegegner, im Hinblick auf die erlebnismässige Verarbeitung eines Unfalls zu einer Gruppe mit erhöhtem Risiko gehören, weil sie aus versicherungsmässiger Sicht auf einen Unfall nicht optimal reagieren (<ref-ruling> mit Hinweis; RKUV 1999 Nr. U 335 S. 210 in fine, 1998 Nr. U 297 S. 245 Erw. 3c).

Demnach erkennt das Eidg. Versicherungsgericht:
I. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
II. Es werden keine Gerichtskosten erhoben.
III. Die Beschwerdeführerin hat dem Beschwerdegegner für
das Verfahren vor dem Eidgenössischen Versicherungsge-
richt eine Parteientschädigung von Fr. 2500.- zu be-
zahlen.
IV. Dieses Urteil wird den Parteien, dem Obergericht des
Kantons Schaffhausen und dem Bundesamt für Sozialver-
sicherung zugestellt.
Luzern, 19. Dezember 2000
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der III. Kammer:
Der Gerichtsschreiber: