logo标签列表

Java单向链表-将现有的对象（节点）移动到末尾位置

java
3
我正在完成一个与链表相关的小项目。我还有一个方法要完成，然后就完成了。我已经完成了以下所有方法。
  • 添加到前面
  • 添加到后面
  • 删除前面的节点
  • 删除后面的节点
  • 删除指定位置的节点
  • 删除指定节点之前的节点
  • 删除指定节点之后的节点
  • 将当前节点移动到链表末尾
最后一个方法是moveRear方法。
public void moveRear(int index) {
    if (index < 1 || index > size || index == 1 || index == size) {
        System.out.println("Conditions are not met");
        return;
    }
    if (head == null) {
        System.out.println("List is empty");
        return;
    }
    Node cNode = null;
    Node pNode = null;
    cNode = head;
    for (int i = 1; i < index - 1; i++) {
        cNode = cNode.next;
    }
    pNode = head;
    while (pNode.next != null) {
        pNode = pNode.next;
    }
    cNode = cNode.next.next;
    pNode = cNode.next;
    tail = cNode.next;
}

我需要将前一个节点链接到我要移动的节点后面。例如，我想把节点3移到链表的尾部。这意味着我需要让节点2链接到节点4以保持链表连接。然后我需要让最后一个节点指向节点3，最后使TAIL指向它。

你的链表索引是从0开始还是从1开始？我问这个是因为你方法中的第一个if语句。 - Chris Gong
1
这个程序中的每个方法索引都从1开始而不是0。在这种情况下，我进行了索引-1，因为我想获取我想要移动的节点之前的节点的引用，以便重新连接链接列表。我不确定为什么我在这里得到了一个踩。 - SkyZ
在移动3之前，将2链接到4？ - Adrian M.
当我将pNode = cNode.next移到顶部时，我仍然得到相同的输出。 - SkyZ
3个回答
1
此外，根据您现在的操作，您正在更新引用但未更改节点的“next”字段。因此，您只是重置某些变量指向的内容。您实际上没有更改cNode和pNode的下一个字段，而只是更改了名为cNode和pNode的变量所指向的内容。相反，您应该更新cNode.next和pNode.next。
现在考虑尾节点的特点。
1. 尾部的“next”字段始终为null
此外，考虑两种对于此方法不同寻常的情况。
1. 您想将前面移至后面（索引==1） 2. 您想将后面移至后面（cNode.next == tail）
在第一种情况下，您不仅需要执行正常操作，还需要重置front变量。在第二种情况下，您不需要做任何事情，因为rear已经在后面。假设cNode表示要移至后面的节点之前的节点，pNode表示以前的rear，则所有内容如下：
public void moveRear(int index) {
    if (index < 1 || index > size || index == size) {//You actually have already 
                                                     //dealt with special case #2
        System.out.println("Conditions are not met");
        return;
    }
    if (head == null) {
        System.out.println("List is empty");
        return;
    }
    Node cNode = null;
    Node pNode = null;
    cNode = head;
    for (int i = 1; i < index-1; i++) {
        cNode = cNode.next;
    }
    pNode = head;
    while (pNode.next !=null){
        pNode = pNode.next;
    }
    if(index==1){ //special case #1
        head = cNode.next; //reset the front to the node after the front node
        pNode.next = cNode; //update the former rear's next field
        tail = pNode.next; //update the tail VARIABLE
    }
    else{ //what you would do if it was not either special case
        pNode.next = cNode.next;//reset the former rear's next field first
        cNode.next = cNode.next.next;//then change cNode's next field, ORDER MATTERS HERE
        tail = pNode.next;//then reset the rear VARIABLE

}
0
最后三行代码中出现了错误。变量cNode指向的是你想要移动的节点之前的一个节点（我们称之为target），这是正确的，但是你使用cNode = cNode.next.next;覆盖了它，因此你现在无法更改next值（它应该指向target后面的节点）。另外，由于你将target移动到了列表的末尾，所以你不必再搜索pNode，你已经有了tail。
public void moveRear(int index) {
    if (index < 1 || index > size || index == 1 || index == size) {
        System.out.println("Conditions are not met");
        return;
    }
    if (head == null) {
        System.out.println("List is empty");
        return;
    }

    // search node previous to target
    Node cNode = null;
    cNode = head;
    for (int i = 1; i < index-1; i++) {
        cNode = cNode.next;
    }

    // remember target
    Node target = cNode.next;

    // exclude target from list
    cNode.next = cNode.next.next;

    // add target to the tail
    tail.next = target;
    target.next = null;
    tail = target;
}

如果你想处理 index == 1 的情况，你可以简单地添加以下内容

if(index == 1) {
    Node tmp = head.next;
    tail.next = head;
    head.next = null;
    head = tmp;
    return;
}

在搜索部分之前 (Node cNode = null;)。

public void moveRear(int index) {
    if (index < 1 || index > size || index == size) {
        System.out.println("Conditions are not met");
        return;
    }
    if (head == null) {
        System.out.println("List is empty");
        return;
    }

    if(index == 1) {
        Node tmp = head.next;
        tail.next = head;
        head.next = null;
        head = tmp;
        return;
    }

    // search node previous to target
    Node cNode = null;
    cNode = head;
    for (int i = 1; i < index-1; i++) {
        cNode = cNode.next;
    }

    // remember target
    Node target = cNode.next;

    // exclude target from list
    cNode.next = cNode.next.next;

    // add target to the tail
    tail.next = target;
    target.next = null;
    tail = target;
}
我刚刚自己完成了索引1的情景。对于索引1，我做了一些不同的事情，但代码行数仍然相同。我不确定为什么最后这个方法给我带来了这么多问题。谢谢！ - SkyZ
@SkyZ 如果其中一个答案对您有帮助并解决了您的问题，请将其标记为已接受。 - Nikolay K
0

抱歉，我无法理解pNode和cNode引用变量。

以下是一个完成所需功能的代码。我假设我们正在维护一个tail引用节点，它始终指向列表中的最后一个节点。

public void moveRear(int index) {

    if (index < 1 || index > size || index == 1 || index == size) {
        System.out.println("Conditions are not met");
        return;
    }
    if (head == null) {
        System.out.println("List is empty");
        return;
    }

    Node previousToTheOneWhichNeedsToBeMoved = null;
    previousToTheOneWhichNeedsToBeMoved = head;
    for (int i = 1; i < index - 1; i++) {
        previousToTheOneWhichNeedsToBeMoved = previousToTheOneWhichNeedsToBeMoved.next;
    }

    Node needsToBeMoved = previousToTheOneWhichNeedsToBeMoved.next;

    previousToTheOneWhichNeedsToBeMoved.next = needsToBeMoved.next;
    tail.next = needsToBeMoved;
    needsToBeMoved.next = null;
}

另外，以下是通过的单元测试。下面使用的LinkedList构造函数如下：
LinkedList（Node head，Node tail，int size）
@Test
public void should_TraverseList_Given_3elements(){
    Node one = new Node(1);
    Node two = new Node(2);
    Node three = new Node(3);
    one.next = two;
    two.next = three;
    three.next = null;

    LinkedList list = new LinkedList(one, three, 3);

    assertEquals("123", list.toString());

    list.moveRear(2);
    assertEquals("132", list.toString());
}

@Test
public void should_TraverseList_Given_4elements(){
    Node one = new Node(1);
    Node two = new Node(2);
    Node three = new Node(3);
    Node four = new Node(4);
    one.next = two;
    two.next = three;
    three.next = four;
    four.next = null;

    LinkedList list = new LinkedList(one, four, 4);

    assertEquals("1234", list.toString());

    list.moveRear(2);
    assertEquals("1342", list.toString());
}

注：索引从1开始

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接