Disk Utility: Incorrect number of file hard links

I'm running Mountain Lion on my Mid 2009 MBP. Recently(for last few months) it's acting really slow. Simplest actions are taking forever to perform. So I verified disk using the Disk Utility and it said that Incorrect number of file hard links and The volume Macintosh HD was found corrupt and needs to be repaired. It suggested me to restart and repair. I did that but about a week later it became slow again. I verified again and this time also it gave the same message.

Can I be certain that it's a fault of the HDD and just change it?

Solution 1:

I took the laptop to Apple service centre. They ran few diagnosis and it turns out the hard disk was fine. One of those test results said that the hard disk is corrupted, and it needs to be formatted and repartitioned. So they formatted the HDD and reinstalled the OS. That seems to have fixed it.