• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

an interview problem

 
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anybody can teach me a way to find the mid-node of a single linkedlist without counting the list. ( the more efficient, the better)
[ December 07, 2004: Message edited by: Jingyi Wang ]
 
Sheriff
Posts: 4313
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jingyi-
That sounds an awful lot like a homework assignment. How have you tried to solve the problem? We're more than welcome to help, but we're not going to do your work for you.

Also, please edit the subject of your thread. "help" isn't very descriptive. Click the "edit" link on the top of your thread and put something more applicable to your question.

Thanks!
 
Jingyi Wang
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is not homework. That is an interview problem by some company that I couldn't figure it out even now. So, I just posted here to see if somebody can give an answer. Not a big deal !
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nothing clever comes to mind. Make two pointers, advance the first through the list, advance the second every other time? I'm iterating the list but not counting. Maybe something recursive?
 
Ranch Hand
Posts: 196
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
removeFirst and removeLast until isEmpty returns true.
The last node that is retrieved is the mid-one.
What is wrong with this solution?
 
Ranch Hand
Posts: 5093
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
it destroys the list?

Sounds like a typical homework assignment to me. If an interview question you have to seriously doubt the interviewer as implementation details like that are usually of no consequence in a professional environment...
 
Jingyi Wang
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is single Linkedlist, you are not able to find the last one in the first place
 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Make two pointers, advance the first through the list, advance the second every other time."

Stan's method would work.

Each time the firs pointer advances two nodes in a row, while the second advances one node.

when the first pointer reaches the end, the second reaches the mid-node.

A few minor issues:
Differentiate Odd/Even number of nodes in the list
Definition of mid-node in each case?
the case when the first pointer advances only one node in the last step..

Jim
 
Jingyi Wang
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, this way is better than counting the nodes. Counting the nodes need 1.5N traverses, but this way only need N traverses. Very smart! Anybody else can come up a better way ( less than N traverses? ).
 
Jim Cheng
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, it still traverses 1.5N nodes.

N nodes for the first pointer
0.5N nodes for the second.

Remember that in a single-linked-list, a pointer cannot advance two nodes directly.

Jim
 
Stan James
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You'd need a rule about what the middle is in an even number of nodes, say 2. I didn't try to think through the last odd step. Advance the mid pointer only if two more are present or if only one is present? Hmmm, for a list of 3 we advance 2 and 1, then advance 1 and 0, leaving the midpointer at the 2nd node. I think.
 
Jingyi Wang
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1.5 N, right

[ December 08, 2004: Message edited by: Jingyi Wang ]

[ December 08, 2004: Message edited by: Jingyi Wang ]
[ December 08, 2004: Message edited by: Jingyi Wang ]
 
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For an even-node list, there isn't a mid-node, so return null.
 
And when my army is complete, I will rule the world! But, for now, I'm going to be happy with this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic