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
Post a Comment