Учитывая связанный список чисел. Подкачайте каждые 2 смежных ссылки

Здесь он находится на полностью работающей Java. Это чисто указательная игра.

public class ListSwap {
    // the swap algorithm
    static void swap(Node current) {
        while (true) {
            Node next1 = current.next;
            if (next1 == null) break;
            Node next2 = next1.next;
            if (next2 == null) break;
            Node next3 = next2.next;
            current.next = next2;
            next2.next = next1;
            next1.next = next3;
            current = next1;
        }
    }
    // the rest is infrastructure for testing
    static class Node {
        Node next;
        final char data; // final! Only pointer play allowed!
        Node(char data, Node next) {
            this.data = data;
            this.next = next;
        }
        @Override public String toString() {
            return data + (next != null ? next.toString() : "");
        }
    }

(продолжение ...)

    static class List {
        Node head;
        List(String data) {
            head = null;
            String dataReversed = new StringBuilder(data).reverse().toString();
            for (char ch : dataReversed.toCharArray()) {
                head = new Node(ch, head);
            }
            head = new Node('@', head);
        }
        @Override public String toString() {
            return head.toString();
        }
        void swapPairs() {
            swap(head);
        }
    }
    public static void main(String[] args) {
        String data = "a1b2c3d4e5";
        for (int L = 0; L <= data.length(); L++) {
            List list = new List(data.substring(0, L));
            System.out.println(list);
            list.swapPairs();
            System.out.println(list);
        }
    }
}

( см. Полный вывод )

@dkamins: Вы меняете значения, но в подобных вопросах интервьюеры обычно спрашивают о перестановке указателей.

Моя попытка решить задачу:

void swap (struct list **list1)
{
    struct list *cur, *tmp, *next;
    cur = *list1;

    if(!cur || !cur->next)
              return;

    *list1 = cur->next;

    while(cur && cur->next)
    {
              next = cur->next;
              cur->next = next->next;
              tmp = cur->next;
              next->next = cur;
              if(tmp && tmp->next)
                  cur->next = cur->next->next;
              cur = tmp;                                  
    }
}

Вот приблизительный набросок гораздо более простой версии, предполагая, что Node имеет члены «Next» и «Data»:

  for (Node n = head; n && n.Next; n = n.Next.Next) {
    void* tmp = n.Data;
    n.Data = n.Next.Data;
    n.Next.Data = tmp;
  }

Другими словами, остановитесь на каждом другом узле в списке и поменяйте свои данные следующим (единственным). Простой.

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

Я немного адаптировал решение @dkamins. Вместо того чтобы принимать указатель на указатель, я возвращаю новый head. Я также улучшил его.

struct Node
{
   struct Node *next;
   int data;
};

typedef struct Node * NodePtr;
NodePtr swapEveryTwo(NodePtr head)
{
   NodePtr newHead = (head && head->next) ? head->next : head;
   NodePtr n = head;
   while(n && n->next)
   {
      NodePtr tmp = n;     // save (1)
      n = n->next;         // (1) = (2)
      tmp->next = n->next; // point to the 3rd item
      n->next = tmp;       // (2) = saved (1)
      n = tmp->next;       // move to item 3

      // important if there will be further swaps
      if(n && n->next) tmp->next = n->next;
   }

   // return the new head
   return newHead;
}

По сути, новая голова списка - это либо текущая голова, если NULL или длина 1, либо 2-й элемент.

В цикле подкачки, tmp в конечном итоге станет 2-м элементом, но изначально он первый. Поэтому нам нужно, чтобы он указывал на 3-й элемент, для чего и предназначен tmp->next = n->next;. Я не использую цикл for, потому что в этом случае он будет менее интуитивным - будет казаться, что выражение переоценки перескакивает только на 1 узел за итерацию. В конце цикла while, n = tmp->next; имеет интуитивный смысл - мы указываем на элемент после tmp, второй элемент.

Самая важная часть - это последняя строка. Поскольку мы делаем это в прямом направлении, мы должны помнить, что 2-й элемент предыдущей итерации почти наверняка будет указывать на возможный 4-й элемент текущей итерации, потому что в этой итерации 3 и 4 поменяются местами. Поэтому в конце итерации, если мы понимаем, что в следующей итерации мы снова поменяемся местами, мы спокойно указываем 2-й элемент на текущий 4-й элемент, зная, что в следующей итерации это будет 3-й элемент и все в мире будет хорошо.

Например, если список имеет вид 2 -> 7 -> 3 -> 5:

n = 2
tmp = 2
n = 7
tmp->next = 3 (2 -> 3)
n->next = 2 (7 -> 2)
n = 3
7 -> 2 -> 3 -> 5

but then there will be swaps, so the last statement says
7 -> 2 -> 5      3?

Это нормально, потому что n = 3, так что мы не потеряли этот узел. Следующая итерация:

n = 3
tmp = 3
n = 5
tmp->next = NULL (3 -> NULL)
n->next = 3  (5 -> 3)
n = NULL

Приводит к окончательному ответу 7 -> 2 -> 5 -> 3.