Please Correct My Code :/ I have dry run my code many times still not able to find the error : Even After Odd Problem

#1

import java.util.*;
class LinkedList {
private class Node {
int data;
Node next;

	Node(int data, Node next) {
		this.data = data;
		this.next = next;
	}
}

private Node head;
private Node tail;
private int size;

public LinkedList() {
	this.head = null;
	this.tail = null;
	this.size = 0;
}

public LinkedList(Node head, Node tail, int size) {
	this.head = head;
	this.tail = tail;
	this.size = size;
}

// O(1)
public int size() {
	return this.size;
}

// O(1)
public boolean isEmpty() {
	return this.size() == 0;
}

// O(1)
public int getFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.head.data;
}

// O(1)
public int getLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.tail.data;
}

// O(N)
public int getAt(int idx) throws Exception {
	Node temp = this.getNodeAt(idx);
	return temp.data;
}

// O(N)
private Node getNodeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	Node retVal = this.head;
	for (int i = 0; i < idx; i++) {
		retVal = retVal.next;
	}

	return retVal;
}

// O(1)
public void addFirst(int data) {
	Node node = new Node(data, this.head);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.head = node;
	}

	this.size++;
}

// O(1)
public void addLast(int data) {
	Node node = new Node(data, null);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.tail.next = node;
		this.tail = node;
	}

	this.size++;
}

// O(n)
public void addAt(int idx, int data) throws Exception {
	if (idx < 0 || idx > this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		this.addFirst(data);
	} else if (idx == this.size()) {
		this.addLast(data);
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;

		Node node = new Node(data, n);
		nm1.next = node;

		this.size++;
	}
}

// O(1)
public int removeFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.head.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		this.head = this.head.next;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.tail.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		Node sm2 = this.getNodeAt(this.size() - 2);
		sm2.next = null;
		this.tail = sm2;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		return this.removeFirst();
	} else if (idx == this.size() - 1) {
		return this.removeLast();
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;
		Node np1 = n.next;

		nm1.next = np1;
		this.size--;

		return n.data;
	}
}

// O(n)
public void display() {
	Node node = this.head;

	while (node != null) {
		System.out.print(node.data + " ");
		node = node.next;
	}

	//System.out.println("END");
}
public void evenAfterOdd() throws Exception {
	int n = size;
    Node curr = head;
    for(int i = 0; i<n; i++){
        if(curr.data%2==0){
            addLast(removeAt(i));
        }
        curr = curr.next;
    }

}
public static void main(String[] args) throws Exception {

	Scanner scn = new Scanner(System.in);
	int N = scn.nextInt();

	
	LinkedList list = new LinkedList();

	for (int i = 0; i < N; i++) {
		list.addLast(scn.nextInt());
	}

	list.evenAfterOdd();
	list.display();

}
}

#2

@ap8730390,
https://ide.codingblocks.com/s/254552 corrected code using the approach you took.
Some errors:

  1. Count the number of even numbers, in order to add a condition to break the loop.
  2. See, if you use curr.data%2==0, the element at curr and removeAt(i) will be different. So, just get the element at index i and check if its even. And keep a count on number of even elements you have added at the back. And do count-- and i-- when you move an element to the back of the linked list.

You can try keeping a previous node variable to optimize it futher.

Also something to look out for, the time complexity of your code is quite large as compared to the approach I mentioned below.

https://ide.codingblocks.com/s/254543 corrected code using the approach I have mentioned below.
Algo :

  1. Take Two Fake_heads to take care of odd and even list.
  2. Put loop on the given LinkedList.
  3. If the node is odd add it to odd fake_ head list.
  4. If the node is Even add it to the even fake_head list.
  5. At the set connect both of the list together and set head to odd list.