Both Neji and Shikamaru were assigned to the squad tasked with bringing back Sasuke Uchiha. Despite being older than Shikamaru, Neji soon grew to respect his intelligence and leadership qualities.
In the anime, during the Sasuke Retrieval Mission, Shikamaru was the only one who was shown facing Neji.
Not only that but Neji's opponent (Kidomaru) was shown to have a similar hairstyle to Shikamaru.
Among The Fans
ShikaNeji is a fairly popular yaoi couple with a dedicated and hardcore following. Its fandom has produced a large amount of well-regarded fanfiction such as the Break to Breathe series.
Many fans of the couple point to their similarities with Shikamaru and Neji both being long-haired geniuses who are looked to for leadership roles. While others like the contrast of pairing the lazy, cynical, and snarky Shikamaru with the straight-laced Neji. Their rival couples are ShikaTema, ShikaIno, NejiTen, and NejiHina.