我应该如何实现删除我的自定义Linkedlist的右半部分

Question

写入类LinkedList的成员方法removeRightmostHalf。不要调用类的任何方法，也不要使用任何辅助数据结构。

如果l包含A! B! C! D! E，则调用l.removeRightmostHalf()后，l变为A! B! C。

int size = 0 ; 
int halfSize = 0;
current = head;
while (current.next != null) {
    ++size;
    current=current.next;
}
++size;
if (size % 2 == 0) {
    halfSize = (size / 2);
    for (int i = halfSize + 1; i < size; i++) {
    }
}

我不知道我将如何删除内部for循环。任何帮助!

Answer 1

我建议你使用两个指针，slow和fast指针。一开始，两者都指向链表的起点。

• 慢指针每次移动一个节点。
• fast将每次移动两个节点。

当您看到fast指针到达列表末尾时，只需通过设置next=null;

将慢指针节点标记为列表末尾

需要注意的是，列表末端的发现将取决于列表的偶数/奇数大小。所以设计和测试这两种情况

Answer 2

这是可行的，当你到达列表的一半时，只要切断与其余部分的链接。

public void removeRightMost() {
    int size = 0;
    int halfSize = 0;
    current = head;
    while (current!= null) {
        size++;
        current = current.next;
    }
    if (size % 2 == 0) {
        halfSize = (size / 2);
        int count = 0;
        current = head;
/* if the number of elements is even you need to decrease the halfSize 1 because 
you want the current to reach the exactly half if you have 4 elements the current
should stop on the element number 2 then get out of the loop */
       while (count < halfSize-1) { 
            current = current.next;
            count++;
        }
        current.next=null;      //here the process of the deletion when you cut the rest of the list ,  now nothing after the current (null)
    }
    else {
        halfSize = (size / 2);
        int count = 0;
        current = head;
        while (count < halfSize) {
            current = current.next;
            count++;
        }
        current.next=null;
    }
    current=head;  // return the current to the first element (head)
}

祝你好运