Please, beware! Following the explanations given here will lead you to revert back to a previous system, losing all your recent changes, if any! You must choose...
All is simple if you have at hand:
A disk (floppy, usb key or CD) able to start Linux by itself with fdisk available - most rescue disks of any distribution can do that;
A paper with the fdisk -l and fdisk -u -l content written down.
It's enough to:
Start Linux;
Start fdisk /dev/hda (or whatever is the disk to rescue);
Use fdisk to delete (d option) all the existing partitions on the damaged disk;
Use fdisk to create all the primary (1 - 4) partitions mentioned on the paper;
Give them the appropriate tag (t option) : 82 is for Linux swap, 83 for Linux main (L gives you the list), 5 is extended and must be done before creating logical partitions, c is MS Windows FAT32, and f is MS Windows extended when 6 is MS Windows FAT16.
Create any logical partition.
On my SUSE installation and any time I had to do this for other people, this has produced good results.
However, I said that some fdisks may cut partitions on a sector basis, not cylinder. So the fdisk -u -l version of the paper.
For using the fdisk -u -l listing one must start fdisk -u :-). In my opinion, using sector limit is a very bad idea, but it may have a real use I'm not aware of. The problem is that, with cylinder limit, it's easy to guess even if you don't have paper. With sector one, there are many more guesses...
fdisk is a small and very smart programs. There are many other makes of fdisk, but I always prefer the bare bones 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. If you fear a mistake, hit q (quit) or Ctrl C (^C) to quit safe without saving changes.
When your new partition table is written, start your Linux. It's possible you might not be able to do that as usual: lilo/grub may have been damaged also, and you thus may need a boot floppy or CD. Choose the option "booting the installed partition".
If you are accustomed to booting with lilo, as soon as you are logged in as root, key in "lilo" and hit return to reinstall your favourite boot loader. Right now, I'm not sure that the same thing is as easy with GRUB, but it should not be very difficult, either.
Your Linux should be all here; test it. Try, also, to start MS Windows if applicable. If you can't, there is a (very small) chance you can read your data from Linux, maybe with a raw sector-by-sector read. If you can identify the disk sectors your data is on, using dd you can copy it to 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 work for use of an out-of-date one.
Warning
You can only try primary partitions with no fear. logical partition uses ordinary sectors of the disk to store their own housekeeping data, so, each time you write some logical partition with fdisk, you write some sectors, erasing the data content, if any. There is still a chance you don't have any data there or the data is unimportant, but, the less often you do such tries, the better.
First, be aware that as soon as you don't write to the disk (except with fdisk), you don'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 doesn'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.
If you just destroyed your own partition table, but have not rebooted Linux: Don't reboot! You can still retrieve the partition information stored in the Kernel:
cat /proc/partitions gives
major | minor | #blocks | name |
3 | 0 | 19535040 | hda |
3 | 1 | 2096451 | hda1 |
3 | 2 | 4980150 | hda2 |
3 | 3 | 1 | hda3 <--- this marks an extended partition |
3 | 5 | 4980118 | hda5 |
3 | 6 | 4972086 | hda6 |
hdparm -g /dev/hda1/dev/hda1 :
geometry = 2432/255/63, sectors = 4192902, start = 63
You'll need to do a few unit conversions. "blocks" are usually 1K in length. "Sectors" are disk sectors, often 512 bytes. But usually the disk partitioning tools work in units of cylinders. (Here, 255*63=16065 sectors.) Using this information, you can build a new partition table.
If you know the start of a Linux partition, but not the end, you can still mount it, and learn about the structure. Set the partition table start correctly, and set the end to something very large. See if you guessed correctly with:
e2fsck -n /dev/hd??
You can even mount the partition and check the size:
mount -r /dev/hd?? /mnt df -T
This won't directly tell you where the next partition starts, because of rounding issues. But it can help you get close. Be sure to use the "-n" and "-r" flags, to treat the system as read-only!!!
Some distributions record partition information in a file. Of course, you probably won't be able to get to this file when you need it. But, just in case:
SuSE: /var/lib/YaST/install.inf
(if you are aware of others, please e-mail the maintainer of this document)
But there is a better way if you can still access the Net or have "gpart" on hand. gpart is available in most distribution, at http://freshmeat.net/ or directly from http://www.stud.uni-hannover.de/user/76201/gpart.
Please note that gpart is not gparted - the GNOME partition editor.
"gpart - guess PC-type hard disk partitions" as the first line of the it's man page states (man gpart). And goes on to say:
"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 a very useful 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" exist on an old disk, and gpart tries to do its 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 MS Windows 2000 (a very awful experience in year 2000!). 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.)
gpart is updated on a weekly basis 
and so new versions may be more powerful than I know.
Extended partition information is scattered on the disk, not stored with the primary partition. To recover these often requires more work. The process is:
Scan for the start of the first partition (using gpart's -k option);
Create a temporary primary partition entry with the true start position and a fake end position. (This may drive you to delete an actual primary partition if no one is available - this is risk free if you don't reuse the sectors of the deleted partition);
Use "e2fsk -n", "mount -r", and "df" to determine the true end point. Write this value down (warning: read the man page for each program mentioned, and use the read-only options; you do not want to write to your disk until all partitions are in the correct place);
Repeat this process for each partition to be recovered;
Build a complete new correct partition table.
If your hard drive has errors, you may have real trouble mounting, checking, or using data. (The drive read errors get in the way.) Gpart may not even find it. But if you know the start of the partition, you can easily copy the data to a temporary file stored on a different drive. Sectors with read errors will usually be set to zero by this process:
Copy the partition data to a file. You must know the start block of the partition;
dd if=/dev/hd?? of=/tmp/recover_hd?? bs=512 skip=XXXX count=YYY
XXX is the sector start and YYY the sector count (can be guessed).
Mount the file as a loop file system.
mount -r -t ext2 -o loop /tmp/recover_hd?? /mnt/recover
Use dd_rescue if the disk is really badly damaged.
Partition Magic is a commercial (and proprietary) software 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.
Ralf's original partition-rescue mini HOWTO was essentially based around the use of Partition Magic, so I assume it's a very good solution, if you have valuable data on your Linux partition and little Linux capability. However, there are now much more recent releases of Partition Magic and I think it's better for you to read the manual.
PartedMagic if the tool of choice for any partition work, including recovery. Extremely good product (and open, of course). Read the HOWTO anyway, because you may need it to prevent disasters, but all the tools are on pmagic, this is the best recovery cd ever...