Showing posts with label Find the middle of a given linked list. Show all posts
Showing posts with label Find the middle of a given linked list. Show all posts

## Find the middle node of a given linked list

Given a singly linked list, find the middle NODE of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.
CONDITION:
• Need to traverse the linked list only once.

```public class MiddleNode {

class NODE {

int data;
NODE next;

public NODE(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

MiddleNode obj = new MiddleNode();

int val[] = new int[] { 3, 6, 7, 8, 9, 11, 13, 15, 17, 22, 24, 25, 28};

/* Get middle NODE */
NODE middleNode = obj.getMiddleNode(start);

System.out.println("MIDDLE NODE : "+middleNode.data);
}

/*
* Create linked base based on given array
*/
NODE start = null;
for (int i : val) {
NODE tmp = new NODE(i);
if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}

/*
* Getting middle NODE just by traversing only once
*/
public NODE getMiddleNode(NODE start) {
NODE slow = start, fast = start;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast.next != null) {
slow = slow.next;
}
return slow;
}
}
```

OUTPUT:

```MIDDLE NODE : 13
```