java-拷贝特殊链表：有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？

public class CopySpecialLinkedList {

	/**
	 * 题目：有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？
拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。
假设原来链表为A1 -> A2 ->... -> An，新拷贝链表是B1 -> B2 ->...-> Bn。
为了能够快速的找到pRand指向的节点，并把对应的关系拷贝到B中。我们可以将两个链表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。
当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。
	 */
	public static void main(String[] args) {
		int[] data = { 1, 2, 3, 4, 5 };
		SpecialLinkList sList = new SpecialLinkList();
		SpecialLinkList.Node source = sList.create(data);
		sList.pRand(0, 4);//add 'pRand'
		sList.pRand(1, 3);
		sList.pRand(2, 0);
		sList.pRand(3, 2);
		sList.pRand(4, 1);
		sList.print(source);
		SpecialLinkList.Node dest = sList.copyPNext(source);
		sList.copyPRand(dest, source);
		sList.print(dest);
	}

}

class SpecialLinkList {

	private Node head;

	class Node {
		int val;
		Node pNext;
		Node pRand;

		Node(int val) {
			this.val = val;
		}
	}

	public Node copyPNext(Node source) {
		Node pre = null;// previous node
		Node dest = null;// destination node
		while (source != null) {
			int val = source.val;
			Node cur = new Node(val);// current node
			if (pre == null) {
				pre = cur;
				dest = pre;
			} else {
				pre.pNext = cur;
				pre = cur;
			}
			source = source.pNext;
		}
		return dest;
	}

	public Node copyPRand(Node dest, Node source) {
		Node a = source;
		Node b = dest;
		// create a1-b1-a2-b2...
		while (a != null && b != null) {
			Node tmp = a.pNext;
			a.pNext = b;
			a = b;
			b = tmp;
		}
		// copy pRand
		a = source;
		b = a.pNext;
		while (a.pNext != null) {
			Node tmp = a.pNext.pNext;
			b.pRand = a.pRand.pNext;
			if (tmp == null) {
				break;
			}
			a = tmp;
			b = a.pNext;
		}
		// split a1-b1-a2-b2... to a1-a2...,b1-b2....
		a = source;
		b = source.pNext;
		dest = b;
		while (a.pNext.pNext != null) {
			Node tmp = a.pNext.pNext;
			a.pNext = tmp;
			a = tmp;

			tmp = b.pNext.pNext;
			b.pNext = tmp;
			b = tmp;
		}
		a.pNext = null;
		b.pNext = null;
		return dest;
	}

	// create a linked list.Insert from tail.
	public Node create(int[] data) {
		if (data == null || data.length == 0) {
			return null;
		}
		Node tail = null;
		for (int len = data.length, i = len - 1; i >= 0; i--) {
			Node tmp = new Node(data[i]);
			tmp.pNext = tail;
			tail = tmp;
		}
		head = tail;
		return head;
	}

	// create 'pRand' between posX and posY
	public void pRand(int posX, int posY) {
		if (posX < 0 || posY < 0) {
			return;
		}
		Node nodeX = getNodeAt(posX);
		Node nodeY = getNodeAt(posY);
		if (nodeX != null && nodeY != null) {
			nodeX.pRand = nodeY;
		}
	}

	// get the node at the specific position.The position starts from 0.
	public Node getNodeAt(int pos) {
		if (pos < 0) {
			return null;
		}
		if (head == null) {
			return null;
		}
		Node node = head;
		while (node != null && pos > 0) {
			node = node.pNext;
			pos--;
		}
		return node;
	}
	//print the special linked list,like 1(5)-2(4)-3(1)-4(3)-5(2).'5' is the pRand of '1',and so on.
	public void print(Node node) {
		while (node != null) {
			System.out.print(node.val + "");
			if (node.pRand != null) {
				System.out.print("(" + node.pRand.val + ")-");
			}
			node = node.pNext;
		}
		System.out.println();
	}

}

评论

1 楼 LoadingTerry 2012-10-07  

朋友 你好！我想和你交流java技术，方便留个联系方式吗？