交换单链表中的节点

Question

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;

Answer 1

要做到这一点，您需要交换两件事：将节点作为上一个节点的下一个节点，以及下一个节点。

找到要交换的节点的前两个节点后，请执行以下操作：

交换节点：

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;

Answer 2

为什么交换节点，当你可以交换数据？

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

交换节点，这很难

在这里人们必须思考，所以最好先处理特殊情况，然后只处理i

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，但是在. Next上进行测试，然后进行赋值，使得条件成为暂时状态。如您所见，如果（i 1==j）{...}其他{...}同时处理ith Node和jthNode，则使用单个会更容易。