剑指offer35----复制复杂链表

题目：

请实现一个cloneNode方法，复制一个复杂链表。

在复杂链表中，每个结点除了有一个next指针指向下一个结点之外，还有一个random指向链表中的任意结点或者NULL。

结点的定义如下：

public static class ListNode {

		int val;

		ListNode next;

		ListNode random;

		ListNode(int x) {

			val = x;

		}

	}

思路：

方法1：

复制原始链表上的每一个结点，并通过next连接起来；然后再设置每个结点的random指针。

假设原始链表中某个结点N的random指针指向结点S,那么就需要从头到尾遍历查找结点S，如果从原始链表的头指针开始，经过m步之后达到结点S，那么在复制链表中的结点N'的random指针指向的结点也是距离复制链表s步的结点。通过这种办法就可以为复制链表上的每个结点设置random指针。

时间复杂度：O(N^2)

方法2：

方法1是通过链表查找来得到random指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：

复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的random指针，如果原始链表中结点N的random指向结点S，那么在复制链表中，对应的N'应该指向S'。

时间复杂度：O(N)

根据方法2，我们可以写出代码：

private static ListNode cloneNode(ListNode head2) {

		if (head2 == null) {

			return null;

		}

		Map<ListNode, ListNode> map1 = new HashMap<>();

		ListNode newHead = new ListNode(head2.val);

		map1.put(head2, newHead);

		ListNode head = newHead;

		// 复制节点和next指针

		for (ListNode cur = head2.next; cur != null; cur = cur.next) {

			head.next = new ListNode(cur.val);

			head = head.next;

			map1.put(cur, head);

		}

		head = newHead;

		// 复制random节点

		ListNode ranNode = null;

		for (ListNode cur = head2; cur != null; cur = cur.next) {

			ranNode = map1.get(cur.random);

			head.random = ranNode;

			head = head.next;

		}

		return newHead;

	}

方法3：

在不使用辅助空间的情况下实现O(N)的时间效率。

第一步：根据原始链表的每个结点N创建对应的N'，然后将N‘通过next接到N的后面；

第二步：设置复制出来的结点的random。假设原始链表上的N的random指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->next指向的结点。

第三步：把长链表拆分成两个链表，把奇数位置的结点用next连接起来的就是原始链表，把偶数位置的结点通过next连接起来的就是复制链表。

如图：

根据方法3，我们可以写出代码：

// 不要额外空间的时间复杂度为O(N)

	private static ListNode cloneNode2(ListNode head2) {

		if (head2 == null) {

			return null;

		}

		// 复制节点和next指针

		ListNode cur = head2;

		while (cur != null) {

			ListNode prev = cur.next;

			ListNode clone = new ListNode(cur.val);

			cur.next = clone;

			cur.next.next = prev;

			cur = prev;

		}

		ListNode old = head2;

		ListNode clone = old.next;

		while (clone != null) {

			if (old.random != null) {

				clone.random = old.random.next;

			}

			old = clone.next;

			if (old != null) {

				clone = old.next;

			} else {

				break;

			}

		}

		ListNode res = oddEvenList(head2);

		return res;

	}

上面的代码可以得到图4.10的结构，而这个时候我们希望把链表分开，老的节点和复制的节点各分为一边，于是乎，出现了奇偶节点的变换（LeetCode328题）：

public static ListNode oddEvenList(ListNode head) {

		if (head == null || head.next == null) {

			return head;

		}

		ListNode oddNode = head;

		ListNode evenNode = head.next;

		ListNode cur = evenNode.next;

		ListNode evenTemp = evenNode;

		int index = 3;

		while (cur != null) {

			if (index % 2 == 0) {

				evenNode.next = cur;

				evenNode = evenNode.next;

			} else {

				oddNode.next = cur;

				oddNode = oddNode.next;

			}

			cur = cur.next;

			index++;

		}

		evenNode.next = null;

		return evenTemp;

	}

返回的evenTemp节点就是我们复制链表的第一个节点！

巴特西

剑指offer35----复制复杂链表

题目：

思路：

最新文章

热门文章