HardPython ProgrammingHigh School (11–12)High School (9–10)UndergraduateGeneralPython Going Further › Data StructuresConceptualA-LevelIB
Write a function that finds the value of the middle node of a chain in one pass, without counting…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
Write a function that finds the value of the middle node of a chain in one pass, without counting the length first. For an even number of nodes, give the second of the two middle ones. (Hint: use two names that walk along, one twice as fast as the other.)
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Let slow move one node at a time, and fast two nodes at a time. When fast reaches the end, slow is at the middle.
Check. For 5 nodes, fast takes 2 steps and reaches the last node, while slow is at the 3rd: value 3. For 4 nodes, fast ends past the end, and slow is at the 3rd node: value 3, the second of the two middle ones. For one node, the loop does not run: 7.
Answer: 3, 3 and 7.
Discussion (0)
Log in to join the discussion.
Loading…