Как перевернуть каждый элемент k связанного списка?

Возможный дубликат:
Обратить каждые k узлы связанного списка

Скажем, связанный список ‹1,3,6,4,8,9,0,2>. Вызов reversek(3) приведет к ‹6,3,1,9,8,4,2,0>. Я написал обратную функцию, которую можно использовать в качестве вспомогательной функции в reversek. Вот моя обратная функция, которая переходит от заданной начальной точки к заданной конечной точке:

    void List::reverse(Node * & start, Node * & end)
    {
    Node *pter = start;
    while (pter != NULL) 
    {
         Node *tmp = pter->next;
         pter->next = pter->prev;
         pter->prev = tmp;
         if (tmp == NULL) 
         {
            endPoint = startPoint;
            startPoint = pter;
         }
       pter = tmp;
    }

Я не понимаю, как реализовать реверсек, любая помощь приветствуется.


person SKLAK    schedule 26.09.2012    source источник
comment
Почему в вашем примере меняются местами последние 2 значения узла?   -  person Mahesh    schedule 27.09.2012
comment
в конце начальный указатель должен указывать на новую голову массива   -  person SKLAK    schedule 27.09.2012
comment
piotrnycz, это не мой пост, совсем другой.   -  person SKLAK    schedule 27.09.2012
comment
@SKLAK Разве это не должно быть 6,3,1,9,8,4,0,2 для вашего примера?   -  person Mahesh    schedule 27.09.2012
comment
@ Махеш, нет, даже эти два последних элемента нужно поменять местами.   -  person SKLAK    schedule 27.09.2012
comment
@SKLAK: ваш это пост или нет, не имеет значения, этот вопрос уже задавался и предлагались различные решения.   -  person Matthieu M.    schedule 27.09.2012


Ответы (1)


Попробуйте что-то вроде -

  1. Имейте 2 указателя (P1, P2) на элемент заголовка связанного списка.
  2. Один используется для обхода списка (P1). В то время как другой (P2) используется для замены элементов, как только точка пересечения достигает 3-го узла в списке.
  3. Теперь переместите оба указателя на 4-й узел. И снова продолжайте P1, просматривая остальную часть списка.

Здесь вы должны отслеживать, когда P1 достигает каждого третьего узла. Здесь, например, 3, но это зависит от аргумента функции.

person Mahesh    schedule 26.09.2012