Palindromų paieška susietame sąraše

Tai interviu klausimas (dar kartą).

Atsižvelgdami į atskirai susietą susietą sąrašą, raskite didžiausią palindromą sąraše. (Galima manyti, kad palindromo ilgis yra lygus)

Pirmasis požiūris, kurį atlikau, buvo rietuvė - mes nuo pat pradžių pereiname sąrašą ir vis spausdiname raides. Kai tik randame, kad raidės viršuje viršuje yra tokia pati kaip kita raidė susietame sąraše, pradėkite spragtelėti (ir didinkite susieto sąrašo rodyklę) ir nustatykite skaičių atitinkančių raidžių. Radę neatitikimą, nustumkite visas raides, kurias iššokote iš rietuvės, ir tęskite stūmimo ir iškėlimo operacijas. Blogiausias šio metodo sudėtingumas būtų O (n2), pvz. kai susietas sąrašas yra tik tų pačių raidžių eilutė.

Norėdami pagerinti erdvės ir laiko sudėtingumą (pagal tam tikrus pastovius veiksnius), aš pasiūliau nukopijuoti susietą sąrašą į masyvą ir surasti didžiausią matricoje palindromą, kuris vėl užima O (n2) laiko sudėtingumą ir O (n) kosmoso sudėtingumas.

Bet koks geresnis būdas man padėti? :(