Please, beware ! following the explanations given here will lead you to turn back to a previous system, loosing all your recent installed one, if any ! You must choose...
All is simple if you have at hand :
It's enough to
fdisk is a small and very smart programs. There are many other makes of fdisk, but I always prefer the bare bone one (I speak of Linux ones, of course, not the others...).
Be aware that fdisk doesn't write anything to disk before you hit w and return. In case you fear a mistake, hit q (quit) or Ctrl C (\^{ }C) to quit safe.
When your new partition table is written, start your Linux. Chance is you can't do that as usual : lilo can have been damaged also and you will need a boot floppy or booting from a cd (choose the option "booting the installed partition").
If you use to boot with lilo, as soon as you are logged in as root, key in "lilo" and hit return to reinstall you favourite boot loader.
Your Linux should be all here, test it. Try also to start windows if applicable. If you can't, there is a (very little) chance you can read your data from Linux, may be with a raw sector by sector read. If you can identify the disk sectors you data is on, using dd can copy them on a file. This is wise for text only. This recovery is NOT in the scope of this mini-HOWTO.
This is when the previous case can't be used, for lack of fdisk paper or if it won't run for use of an out of date one.
First, be aware that as soon as you don't write to the disk (except with fdisk), you can't erase your data, so that you can use a block by block try. That is you need to know the beginning of the partition to start it. If, say a 153 don't fit, try a 154, and so on.
This can be tiresome, but if you remember approximately the size of the Linux partition, there is a chance to win.
But there is a better way if you can still access the net or have "gpart" at hand.
"gpart - guess PC-type hard disk partitions" is the first line of the man page of gpart (man gpart).
"gpart tries to guess which partitions are on a hard disk. If the primary partition table has been lost, overwritten or destroyed the partitions still exist on the disk but the operating system cannot access them.". This is exactly what we need.
gpart is still beta, but is already a very good tool.
The problem is the following : the first block of any partition is marked. But it's never "unmarked" if not overwritten. So many "first partition block" are existing on an old disk and gpart tries to do it's best guessing what is the good one. In fact it's not too difficult to try, nothing is written on the disk by gpart.
Here is the result of gpart on the previously seen disk hdb :
root@charles:/home/jdd > gpart /dev/hdb
Begin scan...
Possible partition(Linux ext2), size(1200Mb), offset(0Mb)
Possible partition(Windows NTFS), size(1200Mb), offset(1200Mb)
Possible partition(Linux ext2), size(1004Mb), offset(2402Mb)
Possible partition(Windows NTFS), size(1600Mb), offset(4102Mb)
End scan.
Checking partitions...
* Warning: partition(OS/2 HPFS, NTFS, QNX or Advanced UNIX) ends beyond disk end .
Partition(Linux ext2 filesystem): primary
Partition(OS/2 HPFS, NTFS, QNX or Advanced UNIX): primary
Partition(Linux ext2 filesystem): primary
Partition(OS/2 HPFS, NTFS, QNX or Advanced UNIX): invalid primary
Ok.
Guessed primary partition table:
Primary partition(1)
type: 131(0x83)(Linux ext2 filesystem)
size: 1200mb #s(2457880) s(63-2457942)
chs: (0/1/1)-(152/254/61)d (0/1/1)-(152/254/61)r
Primary partition(2)
type: 007(0x07)(OS/2 HPFS, NTFS, QNX or Advanced UNIX)
size: 1200mb #s(2457880) s(2457944-4915823)
chs: (152/254/63)-(305/253/60)d (152/254/63)-(305/253/60)r
Primary partition(3)
type: 131(0x83)(Linux ext2 filesystem)
size: 1004mb #s(2056256) s(4919781-6976036)
chs: (306/61/49)-(434/60/47)d (306/61/49)-(434/60/47)r
Primary partition(4)
type: 000(0x00)(unused) size: 0mb #s(0) s(0-0) chs: (0/0/0)-(0/0/0)d (0/0/0)-(0/0/0)r
As you see, primary partition can be recovered, but for extended ones it's still to be done.
Dos partitions are labelled "windows NTFS" because they were created while trying to install Windows 2000 (a very awful experience !). The "invalid" one is, in fact the extended partition.
With this, one can use fdisk and try re-creating the partition table (remember, this is risk-free given the original one is already lost).
Partition Magic is a commercial product, not so cheap given the little use one can have (approx a hundred bucks in France) but with a very high reputation all around there. However I never use it and will not rate it. It's said to be able to do anything with partitions, including restoring them.
Original Ralf partition-rescue mini HOWTO was essentially based around the use of Partition Magic, so I presume it's a very good solution if you have valuable data on your Linux partition and little Linux capability. However there are now very recent makes of Partition Magic and I think it's better for you to read the manual.