Pairwise swap связанного списка

Question

Я пытался сделать парную своп элементов связанных элементов. Вместо обмена данными по элементам я обмениваю их, заменяя ссылки.

С # код:

public LinkedList pairWiseSwapLinks(LinkedList ll) 
{ 
    LinkedList curr = ll; 
    LinkedList next = curr.nextNode; 

    ll = curr; 

    while (curr.nextNode != null && next.nextNode != null) 
    { 
     curr.nextNode = next.nextNode; 
     next.nextNode = curr; 

     Console.WriteLine(curr.data); 
     Console.WriteLine(next.data); 

     curr = curr.nextNode; 
     next = curr.nextNode; 

     Console.WriteLine(curr.data); 
     Console.WriteLine(next.data); 
    } 

    return ll; 
} 

Вход является: 1 -> 3 -> 10 -> 14 -> 16 -> 20 -> 40 Выход: 1 -> 10 -> 16 -> 40

Может кто-нибудь помочь мне с какой ошибкой я делаю?

Answer 1

Есть 2 вопроса:

1. после всех свопов, ваш первый узел должен быть 3, а не 1, в вашем случае, так что вы должны вернуть первоначально второй узел (что, если есть только один?).
2. Причина, по которой 14 пропущена в вашем случае, состоит в том, что в каждом свопе вы включаете только 2 узла в качестве пары. Итак, что происходит после первого свопа, так это то, что список становится 3 -> 1 -> 10 -> 16 ... и 14 -> 10 -> 16, так что вы потеряли 14 (т. Е. Вы не изменили «nextNode» «ref в узле 1, который в этом случае должен быть указан на 14).

Я не хочу, чтобы дать вам прямое решение здесь, но я могу дать вам несколько советов:

1. Вы должны включать в себя 3 узлов в каждом обмене.
2. Однако, если есть только 1/2 узла?
3. Добавление всех угловых случаев в ваш код сделает его незаметным, так что, если я добавлю фиктивный узел в голову списка, чтобы в итоге я мог просто написать «return dummy.next» вместо того, чтобы беспокоиться о поиске текущего первого узел?