Permutation de nœuds dans une liste à liens uniques java

Question

Permutation de nœuds dans une liste à liens uniques java

J'ai essayé de trouver l'algorithme pour échanger 2 nœuds (pas nécessairement juste à côté l'un de l'autre) dans une liste chaînée pendant 2 jours, mais pour une raison quelconque, je ne peux pas le faire. voici ce que j'ai. Je suis vraiment nouveau dans le codage et j'ai été vraiment stressé J'ai réussi à placer un nœud temporaire mais je ne peux pas réellement échanger les nœuds.

public void swap(int i, int j){
current = head;
current2 = head;
sllNode temp = new sllNode(" ");
sllNode temp2 = new sllNode(" ");
for(int z = 0; i>z; z++)
    current=current.next;
for(int q = 0; j>q; q++)
    current2 = current2.next;

temp.next = current2.next.next;
current.next = temp;
current.next = current2.next.next;
current2.next = current;

0

French java linked-list

Author: Mike, 2016-10-24

Source

2 answers

score 1 · Answer 1

Pourquoi échanger des nœuds, quand vous pouvez échanger les données?

public void swap(int i, int j) {

    sllNode ithNode = head;
    for (int z = 0; z < i; z++) {
        ithNode = ithNode.next;
    }

    sllNode jthNode = head;
    for (int q = 0; q < j; q++) {
        jthNode = jthNode.next;
    }

    // Swap the data        
    String data = ithNode.data;
    ithNode.data = jthNode.data;
    jthNode.data = data;
}

, Il serait logique d'utiliser une méthode:

public sllNode get(int i) {
    sllNode current = head;
    while (i > 0) {
        current = current.next;
    }
    return current;
}

Au fait:

La convention pour les noms de classe est une capitale de début: SllNode.
N'utilisez pas de champs pour des choses comme current et current2 où ils peuvent être des variables locales.

l'Échange de nœuds, à la dure

Ici, il faut penser, il est donc préférable de traiter d'abord des cas particuliers, et alors seulement traiter i < j.

public void swap(int i, int j) {
    if (i >= size() || j >= size()) {
        throw new IndexOutOfBoundsException();
    }
    if (i == j) {
        return;
    }
    if (j < i) {
        swap(j, i);
        return;
    }

    // i < j

    sllNode ithPredecessor = null;
    sllNode ithNode = head;
    for (int z = 0; z < i; z++) {
        ithPredecessor = ithNode;
        ithNode = ithNode.next;
    }

    sllNode jthPredecessor = ithNode;
    sllNode jthNode = ithNode.next;
    for (int q = i + 1; q < j; q++) {
        jthPredecessor = jthNode;
        jthNode = jthNode.next;
    }

    // Relink both nodes in the list:

    // - The jthNode:
    if (ithPredecessor == null) {
        head = jthNode;
    } else {
        ithPredecessor.next = jthNode;
    }
    sllNode jNext = jthNode.next;
    //if (ithNode.next == jthNode) {
    if (jthPredecessor == ithNode) {
        jthNode.next = ithNode;
    } else {
        jthNode.next = ithNode.next;
    }

    // - The ithNode:
    if (jthPredecessor == ithNode) {
    } else {
        jthPredecessor.next = ithNode;
    }
    ithNode.next = jNext;
}

Aucune garantie que la logique est correcte. Il y a des astuces:

    //if (ithNode.next == jthNode) {
    if (jthPredecessor == ithNode) {

Les deux conditions testent si i + 1 == j, mais test sur un .ensuite, puis l'attribution fait de la condition un état momentané. Comme vous le voyez, il aurait été plus facile d'avoir un seul if (i + 1 == j) { ... } else { ... } et de gérer à la fois l'ithNode et le jthNode.

score 0 · Answer 2

Pour ce faire, vous devez échanger 2 choses: le nœud suivant du nœud précédent et le nœud suivant.

Une fois que vous avez trouvé current et current2 qui sont les nœuds précédents des nœuds que vous souhaitez échanger, faites ceci:

Permuter les nœuds:

sllNode tmp = current.next;
current.next = current2.next;
current2.next = tmp;

Puis échangez le suivant:

tmp = current.next.next;
current.next.next = current2.next.next;
current2.next.next = tmp;