CODEWITHSUNDEEP
java
Jaisri_88
Jaisri_88

Reputation: 81

how to arrange all even numbers in front of odd numbers in a linked list

Given a linked list, say {1,2,3,5,6,11,10} I need the output as {2,6,10,1,3,5,11}. The even numbers need to be arranged before the odd numbers.

Upvotes: 1

Views: 3830

Answers (8)

Kuldeep Ghate
Kuldeep Ghate

Reputation: 231

Here I'm posting a logic of arranging the nodes based on positions rather than values. You can use similar logic for your problem by placing the pointer nodes appropriately.

public ListNode oddEvenList(ListNode head) {
//if null 
 if(head == null) return null;

//only one/two node/s present
 if(head.next == null || head.next.next == null) return head;

ListNode even = head, odd = even.next, res = odd;
while(odd!=null && even.next != null && odd.next != null){
    even.next = odd.next;
    even = even.next;
    odd.next = even.next;
    odd = odd.next;
    even.next = res;
}
return head;
}

Upvotes: 0

craftsmannadeem
craftsmannadeem

Reputation: 2933

Here is the Algo/Implementation

public static LinearNode<Integer> seperateEvenAndOddNodes(LinearNode<Integer> head) {
    LinearNode<Integer> tail = head, prevNode=null, currNode = head, nextNode;
    int length = length(head), count = 0;
    boolean allEven = true, allOdd = true;
    //point to the last node, start dumping all nodes after this
    while (tail.next() != null) {
        if (tail.getElement() % 2 == 0) {
            allOdd = false;
        } else {
            allEven = false;
        }
        tail = tail.next();
    }
    // Dont do anything if either all odd or all even
    if (allOdd || allEven) {
        return head;
    }
    // Make sure you don't go in infinite loop, and hence condition to make sure, you traverse limited nodes.
    while (currNode != null && count < length) {
        nextNode = currNode.next();
        //move currNode to the end of list, if it is odd.
        if (currNode.getElement() % 2 == 1) {
            LinearNode<Integer> temp = currNode;
            if (prevNode != null) {
                prevNode.next(nextNode);
                currNode = prevNode;
            } else {
                head = nextNode;
                currNode = null;
            }
            tail.next(temp);
            tail = temp;
            temp.next(null);
        }
        prevNode = currNode;
        currNode = nextNode;
        count++;
    }
    //return the new head, in case the list begins with odd
    return head;
}

Here is the unit tests

@Test
public void seperateEvenAndOddNodesTest() {
    LinearNode<Integer> head = buildLinkedList(2,3,4,1,7,8,9);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 2,4,8,3,1,7,9);

    head = buildLinkedList(9,3,4,1,7,8,2);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 4,8,2,9,3,1,7);


    head = buildLinkedList(1,3,5,7);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 1,3,5,7);

    head = buildLinkedList(2,4,6,8);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 2,4,6,8);
}

Upvotes: 0

Parth
Parth

Reputation: 1

  • Take head pointer in temp and traverse the list using temp
  • As soon as you encounter positive number, create a new node at head, copy the data and delete the node pointed by temp. Head will be pointing to new node, Temp will be pointing to next node.
  • Traverse the list until temp->next != NULL
  • Time Complexity will be O(n) since creation and deletion operation are O(1)

Upvotes: 0

amicngh
amicngh

Reputation: 7899

I think for manipulation better to use ArrayList , you can refer below method which returns your sorted List.

public static List<Integer> sortList(List<Integer> list){
    LinkedList<Integer> sortedList = new LinkedList<Integer>();

    List<Integer> evenList=new ArrayList<Integer>();
    List<Integer> oddList=new ArrayList<Integer>();
    for(Integer i:list){

        if(i%2==0)
            evenList.add(i);
        else
            oddList.add(i);
    }

    Collections.sort(evenList);
    Collections.sort(oddList);
    sortedList.addAll(evenList);
    sortedList.addAll(oddList);


    return sortedList;
}

Input:

[1, 2, 3, 5, 6, 11, 10]

Output:

[2, 6, 10, 1, 3, 5, 11]

Upvotes: 0

Nandkumar Tekale
Nandkumar Tekale

Reputation: 16158

    LinkedList<Integer> list = new LinkedList<Integer>();
    LinkedList<Integer> newlist = new LinkedList<Integer>();
    int[] a = {1,2,3,5,6,11,10};
    for(int i=0;i<a.length;i++) {
        list.add(a[i]);
    }

    for(int i=0,j=0; i<list.size(); i++) {
        if(a[i]%2 == 0) {
            newlist.add(j++, a[i]);
        } else {
            newlist.addLast(a[i]);
        }
    }

    System.out.println(newlist);

Upvotes: 0

John3136
John3136

Reputation: 29266

I'd just run through the list twice:

  • first time through output the evens
  • second time through output the odds

This is going to be O(n) which using comparators etc may not be.

Upvotes: 2

Simon Ejsing
Simon Ejsing

Reputation: 1495

A simple solution is to enumerate all elements of the list and assign them to two different list, say even_list and odd_list depending on the oddity of the numbers. Then sort each list individually using basic sort and finally concatenate the two lists into a new list.

Upvotes: 2

tskuzzy
tskuzzy

Reputation: 36446

One way is to create a new list and then loop through your first list, adding even numbers to the beginning of the new list and odd numbers to the end.

Upvotes: 2

Related Questions