当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-04-20   作者:bylijinnan   来源:转载   浏览:
摘要: public class CopySpecialLinkedList { /** * 题目:有一个特殊的链表,其中每个节点不但有指向下一个节点的指针pNext,还有一个指向链表中任意节点的指针pRand,如何拷贝这个特殊链表? 拷贝pNext指针非常容易,所以题目的难点是如何拷贝pRand指针。 假设原来链表为A1 -> A2 ->... -> An,新拷贝
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();
	}

}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
使用LINUX C实现一个链表,要求:(共30分) (1) 链表节点构成:姓名、分数、下一个节点指针;(9分) (
在阅读c-algorithms代码时,又看到如下的代码(删除单链表中任意一个节点) /* A singly-linked lis
转自<http://blog.sina.com.cn/s/blog_69824c1f0100v4ob.html> struct node { int data; stru
指向指针的指针实现单链表的插入、删除 linus说, 例如,我见过很多人在删除一个单项链表的时候,维
给定一个有环链表,实现一个算法返回环路的开头节点。 这个问题是由经典面试题-检测链表是否存在环
题目: 在给定头结点的单链表中插入以及删除指定节点 这个题目我们遇到这个问题的时候可能会想这个
题目: 在给定头结点的单链表中插入以及删除指定节点 这个题目我们遇到这个问题的时候可能会想这个
可接受任意类型的数据的C语言链表 今天在宣讲会上讲了一下我所写的那个可以接收任意类型的参数类型
每日一贴,今天的内容关键字为链表节点 1 数组合并排序 1.1 合并两个已排序好的数组 需要额定的存储
题目描述: 输入一个链表,输出该链表中倒数第k个结点。 (hint: 请务必使用链表。) 输入: 输入可能
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号