offer_JZ25

题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：

具体做法可以分为四步

第一：输入一个复杂链表，返回结果为复制后复杂链表的head

第二：根据原始链表的每个结点N创建对应的结点N'

第三：设置复制出来结点的random.假设原始结点的随机指向S，复制出来结点的random指向S后一个

第四：把这个长链表拆分成两个链表，奇数位置连接起来就是原始链表，偶数结点连接起来就是复制结点

	public RandomListNode Clone(RandomListNode pHead) {

		CloneNodes(pHead);//根据所给的头结点进行拷贝

		ConnectRandomNodes(pHead);//设置随机值

		return ReConnectNodes(pHead);//返回分好的偶数结点

	}

	// 第一步：根据原始链表的每个结点N创建对应的结点N'

	private void CloneNodes(RandomListNode pHead) {

		RandomListNode node = pHead;//定义一个结点，指向头原来的头结点

		while (node != null) {//只要 原来的 当前结点 不空

			RandomListNode cloneNode = new RandomListNode(node.label);//new一个新的结点，并且结点的值域与原来的结点相同

			cloneNode.next = node.next;//将新的结点的next指向原来的当前结点的下一个结点

			cloneNode.random = null;//random先不管，置空

			node.next = cloneNode;//把原来当前结点的next指向新的结点

			node = cloneNode.next;//把原来的当前结点往后移一个位置，也就是把新的结点的next指向赋值给node

		}

	}

	// 第二步：设置复制出来结点的random.假设原始结点的随机指向S，复制出来结点的random指向S后一个

	private void ConnectRandomNodes(RandomListNode pHead) {

		RandomListNode node = pHead;

		while (node != null) {

			RandomListNode clone = node.next;//偶数位置就是克隆出来的新的结点，也是原来结点的next的指向

			if (node.random != null) {//如果原来的结点的random不是空

				clone.random = node.random.next;//把原来random里面的东西赋值给克隆结点的random；

			}

			node = clone.next;//原来的当前位置往后移

		}

	}

	// 第三步：把这个长链表拆分成两个链表，奇数位置连接起来就是原始链表，偶数结点连接起来就是复制结点

	private RandomListNode ReConnectNodes(RandomListNode pHead) {

		RandomListNode node = pHead;//当前结点指向原来的头结点

		RandomListNode cloneHead = null;//复制的头结点指向空

		RandomListNode cloneNode = null;//当前的复制结点指向空

		// 设置第一个节点

		if (node != null) {

			cloneHead = node.next;//偶数位置就是克隆出来的新的结点，也是原来结点的next的指向，用克隆的头结点指向这个克隆的结点，标记原来结点的下一个结点是克隆结点的头结点

			cloneNode = node.next;//把当前的克隆结点指向原来的当前结点的下一个结点

			node.next = cloneNode.next;//把原来的当前结点的next的指向换成克隆结点指向的结点

			node = node.next;//后移

		}

		while (node != null) {

			cloneNode.next = node.next;//把当前克隆结点的next指向换成原来的当前结点的下一个结点

			cloneNode = cloneNode.next;//当前的克隆结点的位置后移一个结点

			node.next = cloneNode.next;//把原来的当前结点的next指向换成当前克隆结点的下一个结点

			node = node.next;//原来的当前结点后移一个结点

		}

		return cloneHead;

	}

图示：第三步中的

设置第一个结点

// 设置第一个节点

		if (node != null) {

			cloneHead = node.next;//偶数位置就是克隆出来的新的结点，也是原来结点的next的指向，用克隆的头结点指向这个克隆的结点，标记原来结点的下一个结点是克隆结点的头结点

			cloneNode = node.next;//把当前的克隆结点指向原来的当前结点的下一个结点

			node.next = cloneNode.next;//把原来的当前结点的next的指向换成克隆结点指向的结点

			node = node.next;//后移

		}

继续



// 设置第一个节点

		if (node != null) {

			cloneHead = node.next;//偶数位置就是克隆出来的新的结点，也是原来结点的next的指向，用克隆的头结点指向这个克隆的结点，标记原来结点的下一个结点是克隆结点的头结点

			cloneNode = node.next;//把当前的克隆结点指向原来的当前结点的下一个结点

			node.next = cloneNode.next;//把原来的当前结点的next的指向换成克隆结点指向的结点

			node = node.next;//后移

		}

while (node != null) {

			cloneNode.next = node.next;//把当前克隆结点的next指向换成原来的当前结点的下一个结点

			cloneNode = cloneNode.next;//当前的克隆结点的位置后移一个结点

			node.next = cloneNode.next;//把原来的当前结点的next指向换成当前克隆结点的下一个结点

			node = node.next;//原来的当前结点后移一个结点

		}

总结

xxx.next 在等号的左边代表 xxx的next这个尾巴的指向

在等号的右边代表 xxx的next的下一个结点实体

巴特西

offer_JZ25

offer_JZ25

思路：

总结

最新文章

热门文章