CODEWITHSUNDEEP
listlinked-list
ueg1990
ueg1990

Reputation: 1033

Finding middle of single linked list

I had modified my function to take care of the case for even number of nodes, but because of that my code does not work for an odd number of nodes. What is wrong?

public LinkedList findMiddleNode() {
    Node t1 = this.getHeadNode();
    Node t2 = this.getHeadNode();
    LinkedList l = new LinkedList();
    boolean even = false;
    while(t1.getNext() != null) {
        t1 = t1.getNext();
        if(t1.getNext()!= null && t1.getNext().getNext() != null) {
            t1 = t1.getNext();
            t2 = t2.getNext();              
        }
    }
    if(t1.getNext()!=null) 
        l.insertFirst(t2.getElement());
    else {
        l.insertFirst(t2.getElement());
        l.insertLast(t2.getNext().getElement());
    }
    return l;
}

Upvotes: 0

Views: 1754

Answers (2)

ueg1990
ueg1990

Reputation: 1033

@oldrinb: thnx for ur help, here is my updated code:

public LinkedList findMiddleNode() {
    Node t1 = this.getHeadNode();
    Node t2 = this.getHeadNode();
    LinkedList l = new LinkedList();
    boolean even = false;
    while(t1.getNext() != null && t1.getNext().getNext() != null) {
            t1 = t1.getNext().getNext();
            t2 = t2.getNext();              
    }
    if(t1.getNext()==null) 
        l.insertFirst(t2.getElement());
    else {
        l.insertFirst(t2.getElement());
        l.insertLast(t2.getNext().getElement());
    }
    return l;
}

Upvotes: 1

obataku
obataku

Reputation: 29646

/* determine length of list */
int n = 0;
for (Node cur = getHeadNode(); cur != null; cur = cur.getNext()) {
  ++n;
}

/* go half-way */
int m = n / 2;
Node mid = getHeadNode();
while (m > 0) {
  mid = mid.getNext();
  --m;
}

/* if n is odd, both mid and mid.getNext() are the middle */
if ((n % 2) != 0) {
  Node mid2 = mid.getNext();
  ...
} else {
  ...
}

... or, alternatively,

Node tortoise = getHeadNode();
Node hare = getHeadNode();

do {
  tortoise = tortoise.getNext();
} while (hare.getNext() != null && (hare = hare.getNext().getNext()) != null);

/* tortoise is the middle */

Upvotes: 0

Related Questions