Étant donné une liste de nombres. Swap tous les 2 liens adjacents

Donné une liste de nombres. Swap tous les 2 liens adjacents. Par exemple, si une liste liée donné est:

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

De sortie prévue:

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

Tous les 2 autres liens doivent être inversés.

J'ai écrit une solution ici. Pouvez-vous me suggérer une autre solution. Pouvez-vous commenter ma solution et m'aider à mieux écrire?

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

careercup.com/question?id=2177669
Ouais je l'ai ramassé question à partir de là, mais ont mis en œuvre, à ma façon...je me demandais si je peux obtenir une meilleure solution ici
personne n'a rien dit à propos de pas à l'aide de stockage supplémentaire

OriginalL'auteur Learner | 2010-05-15

algorithm linked-list

Prendre un coup d'oeil à cette C++ solution:

public void exchangeAdjElements(){
    LLMain backup=current.next;
    LLMain temp = current.next;
    LLMain previous=current;
    while(current!=null && current.next!=null){
        previous.next=current.next;
        current.next=temp.next;
        temp.next=current;
        if(current.next!=null){
            previous=current;
            current=current.next;
            temp=current.next;
        }
    }
    current=backup;
}

Ici le courant est le nœud de tête.

OriginalL'auteur Vyaasprashanth

2

Voici un croquis d'une version beaucoup plus simple, en supposant que le Nœud a "Suivant" et "Données" les membres:
```
  for (Node n = head; n && n.Next; n = n.Next.Next) {
    void* tmp = n.Data;
    n.Data = n.Next.Data;
    n.Next.Data = tmp;
  }
```
En d'autres termes, s'arrêter à chaque autre noeud dans la liste et de swap de ses données avec le suivant (celui). Simple.

Edit: au-Dessus de la solution de swaps de données dans les nœuds, mais pas les nœuds eux-mêmes. Si vous souhaitez échanger des nœuds réels, la solution exige la plus logique.

pourquoi u permutation de données...les nœuds doivent être échangés...pas de données
L'échange de données.? PAS de. PAS de. PAS de.! Vous êtes censé swap nœuds.
Ses mentionner clairement dans la question "Tous les 2 autres liens doivent être inversés." Mais cette réponse est d'échanger les données qui ne sont pas des nœuds.

OriginalL'auteur dkamins

@dkamins: U sont en train de changer les valeurs, mais dans ce type de questions, les enquêteurs demandent généralement pour un pointeur de brassage.

Une tentative de ma part pour le problème:

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

OriginalL'auteur Akash

Ici, il est en complète exécutable Java. C'est purement pointeur de jouer.

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() : "");
        }
    }

(suite...)

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

(voir plein de sortie)

OriginalL'auteur polygenelubricants

0

J'ai adapté @dkamins solution, dans un sens. Au lieu de prendre un pointeur vers un pointeur, je retourne la nouvelle head. J'ai aussi renforcé.
```
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;
}
```
Fondamentalement, la nouvelle tête de la liste est la tête si NULL ou de la longueur de 1 ou de la 2ème élément.

Dans le swap, boucle, tmp finira par devenir le 2ème élément, mais au départ, c'est la première. Nous devons donc à point pour le 3ème élément, qui est le but de tmp->next = n->next;. Je n'utilise pas un for boucle parce que si nous le faisions, il est moins intuitif - la réévaluation de l'expression ne semble d'ailleurs se faire sauter par le noeud 1 par itération. À la fin de la while boucle, n = tmp->next; fait sens intuitif - nous le signaler à l'élément après tmp, le 2ème élément.

La partie la plus importante est la dernière ligne. Parce que nous faisons cela dans un sens, nous devons nous rappeler que la précédente itération du 2e élément est presque certainement va être pointant vers l'itération courante éventuelle 4e élément, parce que cette version sera swap 3 et 4. Ainsi, à la fin de l'itération, si nous nous rendons compte que nous allons échanger à nouveau la prochaine itération, nous tranquillement point de la 2ème élément de l'actuel 4ème élément, sachant que la prochaine itération, il sera le 3ème élément et tout va bien dans le monde.

Par exemple, si la liste est 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?
```
C'est ok parce que n = 3, donc nous n'avons pas perdu de ce nœud. Prochaine itération:
```
n = 3
tmp = 3
n = 5
tmp->next = NULL (3 -> NULL)
n->next = 3  (5 -> 3)
n = NULL
```
Menant à la finale 7 -> 2 -> 5 -> 3 réponse.

OriginalL'auteur Phil
0

Je suppose que pour la rendre plus efficace, il serait mieux de prendre un autre argument n dans la fonction.
Ce n est utilisé pour le comte , je.e après combien de compter les noeuds qui doit être changé. dans le cas ci-dessus, n= 2.
Et puis continuez à l'itération jusqu'à ce que vous frappez le n et utilisé l'inverse linklist alog ou récursive inverse linklist algo de le faire.

vide ReverseLinkList(struct noeud* tête, int n)
{
if( tete == null || null <= 0)
retour;
```
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++;
    }
}
```
}

OriginalL'auteur alice7

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

Ça fonctionne!?

Parce que.

dire :

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

Après la boucle

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

et puis.

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

C'est ce que nous nous attendons à ce droit?

Mais u savoir. La chose réelle sera comme.

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

Car u n'a pas changé le 1->lien suivant pour 4! - Il encore des points à 3!

MA VERSION : Cliquez ici

OriginalL'auteur Yash

voici mon code c++: il sera de retour le pointeur vers le échangé liste liée

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

OriginalL'auteur bysreg

private static SList swapAlternateElements(SList n){

    if(n == null)
        return n;
    SList head = swap(n);
    SList tail = head;

    while(tail == null || tail.next != null){
        tail.next.next = swap(tail.next.next);
        tail = tail.next.next;
    }

    return head;

}

private static SList swap(SList n){

    if(n.next == null || n==null){
        return n;
    }
    SList current = n.next;
    SList next = current.next;
    n.next = next;
    current.next = n;
    return current;

}

OriginalL'auteur user3209952

J'ai essayé de le résoudre, et voici la solution.

public Node swapAdjacentNodes() {
    if (head == null)
        return null;
    if (head.nextNode == null)
        return head;
    Node previous = null;
    Node current = head;
    Node next = head.nextNode;
    while (next != null && next != current) {
        current.nextNode = next.nextNode;
        next.nextNode = current;
        if (previous == null) {
            previous = next;
            head = previous;
            previous = previous.nextNode;
        } else {
            previous.nextNode = next;
            previous = previous.nextNode.nextNode;
        }
        current = current.nextNode;
        if (current == null)
            break;
        next = next.nextNode.nextNode.nextNode;

    }
    return head;

}

OriginalL'auteur fahadkaleem

Voici ma fonction C pour échanger des liens alternatifs de nœuds dans la liste chaînée.J'ai inclus des commentaires dans le code. Pour mieux comprendre prenons un exemple, et courir à travers les étapes en faisant des diagrammes à l'aide de la plume et du papier.

 void swap_alternate_nodes(struct node **head)
    {
        if(*head==NULL)
            return;
        if((*head)->next==NULL)
            return;

        struct node *prev = *head;
        struct node *curr = (*head)->next;
        struct node *temp = NULL;
        *head = (*head)->next; //new head will be second node
        while(curr!=NULL && prev!=NULL)
        {
            if(temp!=NULL)
                temp->next = curr; //previous prev node pointer should point to curr pointer

            prev->next = curr->next; //update prev node pointer

            curr->next = prev; //update curr node pointer

            temp = prev; //store prev pointer

            prev = prev->next; //forward prev pointer

            if(prev)
                curr = prev->next; //forward curr pointer
        }
    }

OriginalL'auteur learner

Mon point de vue sur la solution:-

public Node exchangeAdjacentNodes(Node head){
     Node curr = head;
     Node temp=null,next=null;
     if(curr==null||curr.next==null){
         return curr;
     Node head = curr.next;
     while(curr!=null && curr.next!=null){
           next = curr.next;
           curr.next=next.next;
           temp = curr.next;
           next.next = curr;
           if(temp!=null && temp.next!=null)
                 curr.next = curr.next.next;
           curr=temp;
      }
      return head;
}

OriginalL'auteur Raj Hassani

Ici, le "chef" est le pointeur vers le premier nœud de la Liste Liée et la fonction renvoie la nouvelle tête de pointeur.

node* swapPairs(node *head) {
if(head==NULL || head->next==NULL) {
    return head;
}

node *ptr1=head->next;
node *ptr2=ptr1->next;
ptr1->next=head;
head->next=swapPairs(ptr2);
return ptr1;

}

OriginalL'auteur rohit27kr

public void swapAdjacent() {
    temp = head;
    while (temp != null && temp.next != null) {
        Object tem = temp.val;
        temp.val = temp.next.val;
        temp.next.val = (Object) tem;
        temp = temp.next.next;
    }
}

OriginalL'auteur Sujeet

Il pourrait aider :
public static void main(String[] args) {

    String arr[] = { "a", "b", "c", "d", "e", "f" };
    int i = 0;
    int k = 1;
    String temp;

    while (k <= arr.length - 1 && arr[i] != null && arr[k] != null) {

        temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;

        k++;
        i = k;
        k++;
    }
    for (int j = 0; j < arr.length; j++) {

        System.out.print(arr[j]+"->");
    }

}
//Input  ->  a->b->c->d->e->f->
//Output -> b->a->d->c->f->e->

OriginalL'auteur Gaurav Sharma

C Code d'échanger Adjacentes

node *SwapAdjacent(node *root)
{
    *NextNode = NULL;
    node * result = root->next;
    node *prev = NULL;
    while (root != NULL && root->next!=NULL)
    {
        if(prev!=NULL)
            prev->next= root->next;
        NextNode = root->next->next;
        root->next->next = root;
        root->next = NextNode;
        prev = root;
        root = NextNode;
    }
    return result;
}

OriginalL'auteur amit kumar

Vous devez vous connecter pour publier un commentaire.