链表子列表方法-java [英] linked list sublist method-java

问题描述

我正在尝试编写一个subList方法，该方法返回一个列表，该列表包含当前对象列表，包括在索引 fromIndex 和 toIndex 之间.

I am attempting to write a subList method, which returns a list consisting of the current object list inclusively between indexes fromIndex and toIndex.

例如，如果我的列表包含

For example, if I had list consisting of

3 5 7 9 11 20 23

3 5 7 9 11 20 23

，我叫 subList(0,3)，我应该得到一个新列表

and I called subList(0,3), I should get a new list of

3 5 7 9

3 5 7 9

返回.

我正在使用辅助方法来帮助编写方法.我编写此方法的逻辑是，我将头节点分配为索引为 fromIndex 的节点，同时将列表中的最后一个节点分配为索引为 toIndex 的节点，但什么也没有退还.感谢您的帮助！

I am using helper methods to assist in writing the method. My logic in writing this method is that I assign the head node to to be the node at index fromIndex while assigning the last node in the list to the node at index toIndex, but nothing gets returned. Any help is appreciated!

我创建了一个添加方法，该方法将节点添加到列表中.我仍在尝试编写自己的subList方法来工作.

I am created an add method that that adds nodes to a list. I am still trying to write my own subList method to work.

我更新了一些代码，可以在底部看到它们(忽略上面的旧代码).fromIndex和toIndex包含在新的子列表中.

I have updated some codes, which can be seen at the bottom (disregard older ones above). The fromIndex and toIndex are inclusive in the new sublist.

private class Node<N extends Comparable<N>> {
    private N data;
    private Node<N> next;
}

private Node<L> head;

public List() {
    head=null;
}   

public void add(Node<L> node) {
        Node<L> add = new Node<L>();
        add.data = node.data;
        add.next = null;
        getFinal().next = add;
    } 

public Node<L> getFinal(){
    Node<L> node = head;
    while (node.next != null) {
        node = node.next;
    }
    return node;
}

public int size() {
    if (head == null) return 0;
    int counter = 0;
    for (Node<L> curr = head; curr != null; curr = curr.next)
        counter++;
    return counter;
}

public List<L> subList(int fromIndex, int toIndex)
            throws IndexOutOfBoundsException {
        List<L> n=new List<L>();
        Node<L> tail= new Node<L>();
        n.head=nthItem(fromIndex);
        tail=n.getFinal();
        tail=nthItem(toIndex);
        return n;
    }

public Node<L> nthItem(int index) {
    if (index < 0 || index >= size()) 
        throw new IndexOutOfBoundsException();

    Node<L> ptr = head;

    int i = 0;
    while (ptr != null) {
        if (i == index) return ptr;
        i++;
        ptr = ptr.next;
    }

    throw new IndexOutOfBoundsException();
}

---

更新的代码

---

updated code

private void add(Node<L> node) {
        if(head==null){
            head=node;
        } else {
            getFinal().next = node;
        }
    }

public List<L> subList(int fromIndex, int toIndex)
        throws IndexOutOfBoundsException {
    if(fromIndex<0 || fromIndex>size()-1 || toIndex<0 || toIndex>size()-1){ //size() is 1 bigger than max index so I subtract 1 from size() to equal them out
         throw new IndexOutOfBoundsException();
    }

    List<L> n=new List<L>();
    Node<L> startNode = head;
    int counter=0;
    while(startNode!=null){
         if(counter>=fromIndex && counter<=toIndex){ //fromIndex and toIndex are inclusive so I've added the equals to them. However, it enters an infinite loop, which I do not understand why.
              n.add(startNode);
         }
         startNode=startNode.next;
         counter++;
    }
    return n;
}

推荐答案

问题1-为什么要这样做?LinkedList很好，不需要重写...

Question 1 - why are you doing this? LinkedList would be fine and doesn't need rewriting...

第2点(或b)-您的子列表函数创建一个新列表，设置其头部，然后设置一个临时变量以包含子列表的所需尾巴...

Point 2 (or b) - your sublist function creates a new list, sets its head and then sets a temporary variable to contain the desired tail of the sublist...

在链接列表中，如果您有一个节点，则该节点从该点开始代表该列表的其余部分.为了解决您的问题，您需要克隆所有节点以创建子列表，将最后一个克隆的尾部设置为null.

In a linked list, if you have a node, then that node represents the remainder of that list from that point onwards. To solve your problem, you would need to clone all the nodes to create your sublist, setting the tail of the last clone to null.

但是为什么呢?

-编辑-阐明答案

public List<L> subList(int fromIndex, int toIndex) {
    Node<L> currentInOriginal = nthItem(fromIndex);

    int count = (toIndex - fromIndex) + 1;

    List<L> newSubList = new List<L>();
    newSubList.head = new Node<L>(current.data);

    Node<L> lastItemInList = newSubList.head;
    int soFar = 1;

    currentInOriginal = currentInOriginal.next;
    while(currentInOriginal!=null && soFar<count) {
        lastItemInList.next = new Node<L>(currentInOriginal.data);
        listItemInList = lastItemInList.next;

        currentInOriginal=currentInOriginal.next;
        soFar++;
    }

    return newSubList;
}

这篇关于链表子列表方法-java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！