tag:blogger.com,1999:blog-8712770457197348465.post3186178078647488509..comments2024-03-17T23:01:26.872-07:00Comments on Javarevisited: How to find Middle Element of Linked List in Java in Single Passjavin paulhttp://www.blogger.com/profile/15028902221295732276noreply@blogger.comBlogger50125tag:blogger.com,1999:blog-8712770457197348465.post-86149546164204292502020-07-01T02:23:15.322-07:002020-07-01T02:23:15.322-07:00Why this method is not one pass?
In this method we...Why this method is not one pass?<br />In this method we are traversing through at most "size of the list" elements.<br />But in the brute force. You need 1.5*(size of the list).<br />Kid_Coderhttps://www.blogger.com/profile/08452213821505576513noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-63009556975220019982020-03-09T07:39:48.053-07:002020-03-09T07:39:48.053-07:00Hello Ken, you need to solve this without using Li...Hello Ken, you need to solve this without using LinkedList class, create your own class with ListNode which has data and reference to another ListNode and then create a linked list form that. javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-85901613516265370882020-03-07T23:56:28.250-08:002020-03-07T23:56:28.250-08:00/**
*How to Find Middle Element of Linked List in .../**<br />*How to Find Middle Element of Linked List in Java in Single Pass.<br />* Works on both even or odd sized linked List<br />* @Author: Kennedy<br />*/<br />import java.util.LinkedList;<br />public class MiddleElement<br />{<br /><br /> public static void main(String []args)<br /> {<br /> //Create a linked list<br /> LinkedList object = new LinkedList();<br />Kennedyhttps://www.blogger.com/profile/02819514168786468014noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-29620617169346798382019-06-17T14:18:56.960-07:002019-06-17T14:18:56.960-07:00package problem.solving.linkedlist.practise;
publ...package problem.solving.linkedlist.practise;<br /><br />public class FindMiddleElement{<br /> <br /> private Node head;<br /> private Node tail;<br /> private int size = 0;<br /> <br /> private class Node{<br /> <br /> T data;<br /> Node next;<br /> <br /> public Node(T data, Node next){<br /> this.data = data;<br /> this.next = next;<br /> }<br /> }<br /> <br /> public int size() {<br Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-39715076156982419442019-06-14T06:27:23.844-07:002019-06-14T06:27:23.844-07:00Hello @Anonymous, yes, the fast and slow pointer a...Hello @Anonymous, yes, the fast and slow pointer approach should also work but just check with list with even and odd length, may require bit consideration. javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-55897482014505864802019-06-14T01:48:09.941-07:002019-06-14T01:48:09.941-07:00Perhaps another way of solving this would be using...Perhaps another way of solving this would be using Floyd's slow and fast pointer's concept. Increment the fast pointer by two at each incremental stage until the next of it is not null and increment the slow pointer by one and you shall find the middle element.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-43972133837000994512019-06-04T10:08:27.652-07:002019-06-04T10:08:27.652-07:00Easiest way to find the middle element.
https://yo...Easiest way to find the middle element.<br />https://youtu.be/EsdVJkf2ivIAnonymoushttps://www.blogger.com/profile/06110420871392106342noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-33539180240978990762019-05-04T11:51:44.940-07:002019-05-04T11:51:44.940-07:00void middleNode(list_t *head, int *val){
i...void middleNode(list_t *head, int *val){<br /> if (!head)<br /> return;<br /> list_t *slow, *fast;<br /> slow=fast=head;<br /><br /> while(fast&&fast->next){<br /> slow=slow->next;<br /> fast=fast->next->next;<br /> }<br /> *val = slow->data;<br />}<br />I am just returning the value of Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-41456132417768272322018-12-15T23:21:56.288-08:002018-12-15T23:21:56.288-08:00Sorry Guys why cant we use this
public class Fin...Sorry Guys why cant we use this <br /><br />public class FindMiddleInList {<br /><br /> public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /><br /> LinkedList list=new LinkedList<>();<br /> IntStream.range(1,11).forEach(i->list.add(i));<br /> <br /> System.out.println(list.get(list.size()/2));<br /> }<br /><br />}<br />Mohithttps://www.blogger.com/profile/08108731188331447087noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-28431365925360267972018-08-22T10:29:20.735-07:002018-08-22T10:29:20.735-07:00Or without extra head, Will it return correct leng...Or without extra head, Will it return correct length?Anonymoushttps://www.blogger.com/profile/15410409522387739453noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-91504418148412153512018-08-22T05:46:51.745-07:002018-08-22T05:46:51.745-07:00@Javin Paul, Why there is extra head when we can c...@Javin Paul, Why there is extra head when we can consider "1" as head?<br />In that case, while loop would look like "while(current != null)" instead of "while(current.next() != null)".Anonymoushttps://www.blogger.com/profile/15410409522387739453noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-18019000643136241052018-05-08T03:33:53.280-07:002018-05-08T03:33:53.280-07:00//Shashikumar J B
public class Middle_Node_Linked_...//Shashikumar J B<br />public class Middle_Node_Linked_List {<br /><br /> public static void main(String[] args) {<br /><br /> LinkedList Checking = new LinkedList<>();<br /><br /> int[] sample = {40, 20, 60, 10, 50, 30};<br /> //int[] sample = {40, 20, 60};<br /> //int[] sample = {40};<br /> for (int i = 0; i < sample.length; i++) {<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-72534523749899636242017-02-04T00:51:28.462-08:002017-02-04T00:51:28.462-08:00I am bit puzzled about this problem and solution. ...I am bit puzzled about this problem and solution. Why did you create your own implementation of LinkedList? I would assume that the question was about java.util.LinkedList. If memory is not an issue than creating an Array from LinkedList would be one pass and much simpler. Yasin Hamidhttps://www.blogger.com/profile/01832358017208591303noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-46163174648627906762016-12-21T23:22:46.325-08:002016-12-21T23:22:46.325-08:00As many have pointed out as this answer is looks n...As many have pointed out as this answer is looks not correct. I am agreeing with them.<br />Please change the title of the quesion @Author, @Javin Paul.<br />Its not one pass it is 1.5 passAslam Anwerhttps://www.blogger.com/profile/14550258550331767607noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-78243276849819191352016-10-09T08:04:43.580-07:002016-10-09T08:04:43.580-07:00what about ArrayList ? if you add all nodes to Arr...what about ArrayList ? if you add all nodes to ArrayList while traversing you solve indexed search and any search question if there is no cycle there . right ?<br /><br />p.s.: why can't I comment using facebook ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-20561752972339849442016-10-03T00:29:57.151-07:002016-10-03T00:29:57.151-07:00Guys let me know if i am wrong but i think followi...Guys let me know if i am wrong but i think following code will give us what we want(assuming the list is even)??.<br /><br />int p = 0;<br /> LinkedList l = new LinkedList();<br /> l.add(0);<br /> l.add(1);<br /> l.add(2);<br /> l.add(3);<br /> l.add(4);<br /> l.add(5);<br /> l.add(6);<br /> <br /> p =(l.indexOf(l.getLast()))/2 ;<br /> <br /> System.out.println(l.get(p));Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-88259892240178080502016-07-14T14:41:18.961-07:002016-07-14T14:41:18.961-07:00I wrote this function to find the middle element. ...I wrote this function to find the middle element. I am getting the results:<br />public void middleElement(){<br /> int length = 0;<br /> Node middle = head;<br /> Node current = head;<br /> while(current.next!=null){<br /> length++;<br /> if(length%2==0){<br /> middle = middle.next;<br /> }<br /> current = current.next;<br /> if(length%2 == 1){<br /> current = current.next;<Anonymoushttps://www.blogger.com/profile/03604680129772809694noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-28897903754251257642016-05-29T01:27:25.126-07:002016-05-29T01:27:25.126-07:00@Joshua, you may be right. I guess the pass initia...@Joshua, you may be right. I guess the pass initially refer to how many loop you use to find the middle element of linked list, but you are right, it's not the correct word. A pass can also means accessing the linked list twice. javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-7137401256200914342016-05-15T17:40:43.573-07:002016-05-15T17:40:43.573-07:00I have to be honest.... this is a nice solution an...I have to be honest.... this is a nice solution and all but...the real answer is there is no way of completing this with a single pass. Two pointers means you are making two passes. This is the same for all of the implementations I have seen. I think others have echoed the same sentimate and I realize that at some point this could come down to a wording issue. This is not a slight against the testhttps://www.blogger.com/profile/06928900155237483187noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-66143533923059314162016-01-14T04:40:48.033-08:002016-01-14T04:40:48.033-08:00@Huy, Thanks for your code, but I think I suggeste...@Huy, Thanks for your code, but I think I suggested to write JUnit tests for your code to verify if the solution works for a linked list with even number of elements and a list with odd number of elements e.g. linked list with 5 elements.<br /><br />nevermind, good practice anyway.javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-72209275282711837032016-01-13T11:06:22.151-08:002016-01-13T11:06:22.151-08:00Hi jarvin, here's your request. find odd and e...Hi jarvin, here's your request. find odd and even numbers in the list<br /><br />class Numbers {<br /> int N;<br /> Numbers (int R) { N = R;}<br /> public String toString() { return "" + N; }<br /> int getValue() { return N; }<br />}<br /><br />public class FindMiddle {<br /> public static void main(String[] args) {<br /><br />LinkedList Z= new LinkedList<>();Z.add(new NumbersAnonymoushttps://www.blogger.com/profile/18210278122414120036noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-61945110330331761322016-01-13T06:32:05.833-08:002016-01-13T06:32:05.833-08:00/**
*Find below code for finding the middle elemen.../**<br />*Find below code for finding the middle element by two pointer method<br />*/<br /><br />Node nod1 = list;<br /> Node nod2 = list;<br /> while (nod2.next != null) {<br /> if (nod2.next != null)<br /> nod2 = nod2.next;<br /> else<br /> nod1 = nod1.next;<br /> if (nod2.next != null)<br /> nod2 = nod2.next;<br /> else<br /> nod1 = nod1.next;<br /> }<br /> Anonymoushttps://www.blogger.com/profile/15345745717443835281noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-91699776621269622412016-01-13T04:47:15.725-08:002016-01-13T04:47:15.725-08:00@Huy, good solution, try writing some JUnit tests ...@Huy, good solution, try writing some JUnit tests as well to see if your program works on boundary conditions e.g. linked list with even number of elements, odd number of elements etc.javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-89063691089881842492016-01-12T21:11:34.364-08:002016-01-12T21:11:34.364-08:00Hi, my first Java. How to find middle element of L...Hi, my first Java. How to find middle element of LinkedList in one pass.<br />Iterator iterates through the LinkedList always starts at Z.size()/2. The "count" speaks it all. <br /><br />class Numbers {<br /> int N;<br /> Numbers (int R) { N = R;}<br /> public String toString() { return "" + N; }<br />}<br /><br />public class FindMiddle {<br /> public static void main(String[Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-4520383313973689772015-11-22T20:43:42.598-08:002015-11-22T20:43:42.598-08:00// Below there is only one pass, using one ListIte...// Below there is only one pass, using one ListIterator from head, one desendingIterator from tail<br />public static String findMid2(LinkedList list) {<br /> ListIterator iter1 = list.listIterator(0);<br /> Iterator iter2 = list.descendingIterator();<br /> String fromHead = null;<br /> String fromTail = null;<br /> while (iter1.hasNext()) {<br /> fromHead = iter1.next();<br /> if (AThttps://www.blogger.com/profile/09323052088236837031noreply@blogger.com