15. Middle of the linked list

15. Middle of the linked list


Problem link :- click here


package Linked_List;

public class LinkedList__15
{
	/*
	 	Given a non-empty, singly linked list with head node head, return a middle 
	 	node of linked list.
	 	if there are two middle nodes, return the second middle node.
	 	
	 	we have solved this problem as a sub-problem in the merge sort problem.
	 */
	
	static Node middleNode(Node head)
	{
		if(head == null)
			return head;
		
		Node slow = head;
		Node fast = head;
		while(fast.next != null  && fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		
		if(fast.next == null)
			return slow;
		else
			return slow.next;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		list.push(6);
		
		Node ans = middleNode(list.head);
		System.out.println("Middle node is : " + ans.data);
	}

}

Time complexity :- O(n)
Space complexity :- O(1)

Comments

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree