java combine two linkedlist

Question

I have a question for combining two linkedlist. Basically, I want to append one linkedlist to the other linkedlist.

Here is my solution. Is there a more efficient way to do it without looping the first linkedlist? Any suggestion would be appreciated.

 static Node connect(LinkedList list1, LinkedList list2) {
 Node original = list1.first;
 Node previous = null;
 Node current = list1.first;
 while (current != null) {
 previous = current;
 current = current.next;
 }
 previous.next = list2.first;
 return original;
}

Answer 1

Use list1.addAll(list2) to append list2 at the end of list1.

• caesarkim: I don't want to use standard Java api. I was asked by somebody.
• Kai: If you really want to reinvent the wheel you can look into the sources of the LinkedList of the Collections API how addAll() is implemented.
• Ankit Dixit: @caesarkim addAll() seems to run for loop where it adds all elements from second list to first, having own implementation we can just make head of list1 point to tail of list2, I think that could be the motivation for using own implementation

Answer 2

For linked lists, linkedList.addAll(otherlist) seems to be a very poor choice.

the java api version of linkedList.addAll begins:

public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);
 Object[] a = c.toArray();

so even when you have 2 linked lists, the second one gets converted to an array, then re-constituted into individual elements. This is worse than just merging 2 arrays.

• Indiana Kernick: Seriously?! They provided a LinkedList in their standard library but didn't make it possible to do the things that a linked list can do efficiently? The ability to chop lists up and join them together without memory allocations or copies is the very reason for choosing a linked list. Why did they even bother providing LinkedList then? This seems like more evidence that Java really doesn't care at all about speed or memory usage.

Answer 3

I guess this is your own linked list implementation? With only a pointer to next element, the only way to append at the end is to walk all the elements of the first list.

However, you could store a pointer to the last element to make this operation run in constant time (just remember to update the last element of the new list to be the last element of the added list).

• caesarkim: Yeah. I was thinking the same thing. But the question that I was asked didn't mention anything about the last pointer. I guess that looping for the first linkedlist is inevitable.
• Kai: @caesarkim: Getting the last pointer is why you need your inefficient loop. So the answer is correct in my opinion.

Answer 4

The best way is to append the second list to the first list.

1. Create a Node Class.

2. Create New LinkedList Class.

public class LinkedList<T> {
 public Node<T> head = null;
 public LinkedList() {}
 public void addNode(T data){
 if(head == null) {
 head = new Node<T>(data);
 } else {
 Node<T> curr = head;
 while(curr.getNext() != null) {
 curr = curr.getNext();
 }
 curr.setNext(new Node<T>(data));
 }
 }
 public void appendList(LinkedList<T> linkedList) {
 if(linkedList.head == null) {
 return;
 } else {
 Node<T> curr = linkedList.head;
 while(curr != null) {
 addNode((T) curr.getData());
 curr = curr.getNext();
 }
 }
 }
}

3. In the Main function or whereever you want this append to happen, do it like this.

LinkedList<Integer> n = new LinkedListNode().new LinkedList<Integer>();
 n.addNode(23);
 n.addNode(41);
LinkedList<Integer> n1 = new LinkedListNode().new LinkedList<Integer>();
 n1.addNode(50);
 n1.addNode(34);
n.appendList(n1);

I like doing this way so that there isn't any need for you to pass both these and loop again in the first LinkedList.

Hope that helps

Answer 5

My Total Code:

NOTE: WITHOUT USING JAVA API

class Node {
 Node next;
 int data;
 
 Node(int d){
 data = d;
 next = null;
 }
}
public class OddEvenList {
 
 Node head;
 
 public void push(int new_data){
 Node new_node = new Node(new_data);
 
 new_node.next = head;
 
 head = new_node;
 }
 
 Node reverse(Node head){
 
 Node prev = null;
 Node next = null;
 Node curr = head;
 
 while(curr != null){
 next = curr.next;
 curr.next = prev;
 prev = curr;
 curr = next;
 }
 head = prev;
 
 return head;
 }
 
 Node merge(Node head1, Node head2){
 
 Node curr_odd = head1;
 Node curr_even = head2;
 Node prev = null;
 
 while(curr_odd != null){
 prev = curr_odd;
 curr_odd = curr_odd.next;
 }
 prev.next = curr_even;
 
 return head1;
 }
 
 public void print(Node head){
 Node tnode = head;
 
 while(tnode != null){
 System.out.print(tnode.data + " -> ");
 tnode = tnode.next;
 }
 System.out.println("Null");
 
 }
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 OddEvenList odd = new OddEvenList();
 OddEvenList even = new OddEvenList();
 OddEvenList merge = new OddEvenList();
 
 odd.push(1);
 odd.push(3);
 odd.push(5);
 odd.push(7);
 odd.push(9);
 
 System.out.println("Odd List: ");
 odd.print(odd.head);
 
 System.out.println("Even List: ");
 even.push(0);
 even.push(2);
 even.push(4);
 even.push(6);
 even.push(8);
 
 even.print(even.head);
 
 System.out.println("After Revrse: --------------------");
 Node node_odd =odd.reverse(odd.head);
 Node node_even = even.reverse(even.head);
 
 System.out.println("Odd List: ");
 odd.print(node_odd);
 System.out.println("Even List: ");
 
 even.print(node_even);
 
 System.out.println("Meged: --------------");
 
 Node merged = merge.merge(node_odd, node_even);
 
 merge.print(merged);
 }
}