First you need to stop MySQL and checkservd.
/etc/init.d/mysql stop
Starting MySQL like this will allow anyone access to every database. It may be appropriate to stop eth0, and fuser -k any logged in user, and touch /etc/nologin.
Start MySQL in "Single User Mode" and enter without a password.
mysqld_safe --skip-grant-tables & mysql
Make sure you add the & or you will be stuck with no cmd prompt. Then enter the following commands in the MySQL prompt.
mysql> UPDATE mysql.user SET password=password("123456ABCDEF") WHERE user="root" ;
mysql> exit
If the mysql user has been deleted run the following query to recreate it:
For MySQL 5.0:
INSERT INTO `mysql`.`user` ( `Host` , `User` , `Password` , `Select_priv` , `Insert_priv` , `Update_priv` , `Delete_priv` , `Create_priv` , `Drop_priv` , `Reload_priv` , `Shutdown_priv` , `Process_priv` , `File_priv` , `Grant_priv` , `References_priv` , `Index_priv` , `Alter_priv` , `Show_db_priv` , `Super_priv` , `Create_tmp_table_priv` , `Lock_tables_priv` , `Execute_priv` , `Repl_slave_priv` , `Repl_client_priv` , `Create_view_priv` , `Show_view_priv` , `Create_routine_priv` , `Alter_routine_priv` , `Create_user_priv` , `ssl_type` , `max_questions` , `max_updates` , `max_connections` , `max_user_connections` ) VALUES ( 'localhost', 'root', PASSWORD('password1234'), 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', '0', '0', '0', '0' );
For mysql 4.1:
INSERT INTO user ( `Host` , `User` , `Password` , `Select_priv` , `Insert_priv` , `Update_priv` , `Delete_priv` , `Create_priv` , `Drop_priv` , `Reload_priv` , `Shutdown_priv` , `Process_priv` , `File_priv` , `Grant_priv` , `References_priv` , `Index_priv` , `Alter_priv` , `Show_db_priv` , `Super_priv` , `Create_tmp_table_priv` , `Lock_tables_priv` , `Execute_priv` , `Repl_slave_priv` , `Repl_client_priv`, `ssl_type` , `max_questions` , `max_updates` , `max_connections`) VALUES('localhost', 'root', PASSWORD('&9zKThS'), 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', '0', '0', '0', '0' );
The password should NOT be 123456ABCDEF, make sure it is either the root password or something else. Then stop mysql safe and start normally.
kill %1 /etc/init.d/mysql start
Do a test login.
mysql -u root -p newpass
If you get logged in then you have successfully reset the MySQL root password.