Чтобы решить эту задачу легко - потребуется знать пару приемов для связных списков.

Первый прием- это нахождение середины через fast and slow.
Второй прием -  это merge двух отсортированных связных списков.
Ну и конечно же рекурсию - которая сделает всю магию "разделяй и властвуй".