Clever Geek Handbook

How do I add a linked list to another?

I have implemented my own Linked List structure type, but I am having a problem where I want to add one linked list to another without iterating over anything.

Here is an example with the output I wanted

public class MyList{

    public static void main(String[] args){
        MyList list1 = new MyList(3);
        MyList list2 = new MyList(4);

        System.out.println(list1);  //0 1 2
        System.out.println(list2);  //0 1 2 3

        list1.add(list2);

        System.out.println(list1);  //0 1 2 0 1 2 3
        System.out.println(list2);  //0 1 2 3
    }

    private class Node{
        public int data;
        public Node next;

        public Node(int data){
            this.data = data;
        }
    }

    public Node head;
    public Node tail;

    public MyList(int length){
        for(int i = 0; i < length; i++){
            add(new Node(i));
        }
    }

    public void add(Node node) {
        if (head == null) {
            //insert first node
            head = node;
            tail = node;
        } else {
            //add node to end
            tail.next = node;
            tail = tail.next;
        }
    }

    //Problem!
    public void add(MyList list) {

    } 

    @Override
    public String toString(){
        String result = "";
        for(Node iter = head; iter != null; iter = iter.next){
            result += iter.data + " ";
        }
        return result;
    }   
}

When list2 is added to list1, I want list1 to be expanded without breaking the original list2. I can't figure out how to do this without repeating anything. It is trivial to iterate over list2 in the add method and add each node to the end individually, but this is not relevant to linked lists.

Can anyone give me some advice on how I could do this efficiently

+3


source to share


2 answers


You need to do 2 things:

  • Set the tail.next

    first list

    to the head

    second list

    .
  • and then reassign tail

    from 2 ndlist

    to tail

    from 1 stlist

So this is what your method looks like:



public void add(MyList list) {
    this.tail.next = list.head;
    this.tail = list.tail;
}

And you should better call this method like extend

. This clearly shows the intent of the method.

+9


source


You want to add an head

input list to tail

this list. just write it as code:



public void add(MyList list) 
{
    this.tail.next = list.head;
    this.tail = list.tail;
}
0


source






More articles:


All Articles