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

Question

Приведен связанный список номеров. Поменяйте местами каждые 2 смежные ссылки. Например, если вам предоставлен связанный список:

a->b->c->d->e->f 

Ожидаемый результат:

b->a->d->c->f->e

Каждые 2 альтернативные ссылки должны быть заменены.

Я написал решение здесь. Можете ли вы предложить мне другое решение. Можете ли вы прокомментировать мое решение и помочь мне лучше написать его?

void SwapAdjacentNodes (Node head)
{
    if (head == null) return; 

    if (head.next == null) return; 
    Node curr = head;
    Node next = curr.Next;
    Node temp = next.Next;

    while (true)
    {
        temp = next.Next;
        next.Next = curr;
        curr.Next = temp;

        if  (curr.Next != null)
            curr = curr.Next;
        else
            break;
        if (curr.Next.Next!=null)
            next = curr.Next.Next;
        else
            break;
    }   
}

Answer 1

вот мой код на C ++: он вернет указатель на свопированный список ссылок

Node* swap_list(Node* node) {
if(node == NULL)
    return NULL;

Node* ret = node->next;
Node* pre_a = NULL;
Node* a = node;
Node* b = node->next;   

while(a!=NULL && b!=NULL) {     
    a->next = b->next;
    b->next = a;
    if(pre_a!=NULL)
        pre_a->next = b;
    pre_a = a;
    a = a->next;
    if(a==NULL) break;
    b = a->next;        
}

return ret;
}

Answer 2

void SwapAdjacentNodes (Node head)
{
    if (head == null) return; 

    if (head.next == null) return; 
    Node curr = head;
    Node next = curr.Next;
    Node temp = next.Next;

    while (true)
    {
        temp = next.Next;
        next.Next = curr;
        curr.Next = temp;

        if  (curr.Next != null)
            curr = curr.Next;
        else
            break;
        if (curr.Next.Next!=null)
            next = curr.Next.Next;
        else
            break;
    }   
}

Это работает!?
Потому что.
сказать:

1[cur] -> 2[next] -> 3 [temp]-> 4

После цикла

2 -> 1 -> 3[cur] -> 4[next] -> NULL [temp]

, а затем.

2 -> 1 -> 4 -> 3 ->  NULL

Это то, что мы ожидаем, верно?
Но ты знаешь. Настоящая вещь будет как.

2 -> (1,4) -> 3  -> NULL

Потому что вы не изменили 1-> следующую ссылку на 4! Это все еще указывает на 3!
МОЯ ВЕРСИЯ: Нажмите здесь

Answer 3

Я думаю, чтобы сделать его более эффективным, было бы лучше взять другой аргумент n в функции. Это n используется для подсчета, то есть после того, сколько подсчета необходимо изменить узлы. в вышеприведенном случае n = 2. И затем продолжайте итерацию, пока вы не нажмете n и не используете для этого обратный список ссылок alog или рекурсивный обратный список ссылок algo.

void ReverseLinkList (struct node * head, int n) { if (head == null || null <= 0) возвращение; </p>

struct node* start = head;
struct node* next = null;
struct node* end = head;

int count = 1;

while(end->next != null)
{
    if(count == n)
    {
        next = end->next;
        count = 1;
        //Use ReverseLinklist From start to end
        end->next = next;
        end = next;
        start = next;
    }
    else
    {
        end = end->next;
        count++;
    }
}

}

Answer 4

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

Самая важная часть - последняя строка. Поскольку мы делаем это в прямом направлении, мы должны помнить, что 2-й элемент предыдущей итерации почти наверняка будет указывать на возможный элемент 4th текущей итерации, потому что эта итерация поменяет местами 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 ответу.

Answer 5

Вот он в полностью работоспособной 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);
        }
    }
}

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

Answer 6

@ 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;                                  
    }
}