Блог

Я пытался придумать алгоритм для замены 2 узлов (необязательно рядом друг с другом) в односвязном списке в течение 2 дней, но по какой-то причине я не могу этого сделать. Вот что у меня есть, я действительно новичок в кодировании и был действительно напряжен: Мне удалось разместить временный узел, но на самом деле я не могу поменять местами узлы.

 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;
  

Зачем обмениваться узлами, когда вы можете обмениваться данными?

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

Имело бы смысл использовать метод:

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

Кстати:

• Соглашение об именах классов — это начальная заглавная: SllNode .
• Не используйте поля для таких вещей, как current и current2 , где они могут быть локальными переменными.

Обмен узлами, сложный способ

Здесь нужно подумать, поэтому лучше сначала разобраться с особыми случаями, а потом только лечить 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;
}
  

Нет гарантии, что логика в порядке. Есть хитрости:

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

Оба условия проверяют, является ли i 1 == j , но тестирование на a .next и последующее присвоение делают условие кратковременным состоянием. Как вы видите, было бы проще иметь один единственный if (i 1 == j) { ... } else { ... } и обрабатывать как ithNode, так и jthNode.

Для этого вам нужно поменять местами 2 вещи: узел как следующий из предыдущего узла и следующий узел.

Как только вы нашли, current и current2 которые являются предыдущими узлами узлов, которые вы хотите поменять местами, сделайте это:

Поменяйте местами узлы:

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

Затем поменяйте местами следующий:

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

// Замена двух элементов в связанном списке с использованием Java

импортируйте java.util.*;

класс SwappingTwoElements {

 public static void main(String[] args)
{

    LinkedList<Integer> ll = new LinkedList<>();

    // Adding elements to Linked List
    ll.add(10);
    ll.add(11);
    ll.add(12);
    ll.add(13);
    ll.add(14);
    ll.add(15);

    // Elements to swap
    int element1 = 11;
    int element2 = 14;

    System.out.println("Linked List Before Swapping :-");

    for (int i : ll) {
        System.out.print(i   " ");
    }

    // Swapping the elements
    swap(ll, element1, element2);
    System.out.println();
    System.out.println();

    System.out.println("Linked List After Swapping :-");

    for (int i : ll) {
        System.out.print(i   " ");
    }
}

// Swap Function
public static void swap(LinkedList<Integer> list,
                        int ele1, int ele2)
{

    // Getting the positions of the elements
    int index1 = list.indexOf(ele1);
    int index2 = list.indexOf(ele2);

    // Returning if the element is not present in the
    // LinkedList
    if (index1 == -1 || index2 == -1) {
        return;
    }

    // Swapping the elements
    list.set(index1, ele2);
    list.set(index2, ele1);
}
  

}
Вывод
Перед заменой связанного списка :-
10 11 12 13 14 15

После замены связанного списка:- 10 14 12 13 11 15 Временная сложность: O (N), где N — длина связанного списка