快捷導(dǎo)航

java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例

更新時(shí)間：2023年01月05日 11:12:43 作者：itbird01

這篇文章主要為大家介紹了java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目

AC 劍指 Offer 35. 復(fù)雜鏈表的復(fù)制請(qǐng)實(shí)現(xiàn) copyRandomList 函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè) random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

輸入：head = [[1,1],[2,1]] 輸出：[[1,1],[2,1]]

示例 3：

輸入：head = [[3,null],[3,0],[3,null]] 輸出：[[3,null],[3,0],[3,null]]

示例 4：

輸入：head = [] 輸出：[] 解釋?zhuān)航o定的鏈表為空（空指針），因此返回 null。

提示： -10000 <= Node.val <= 10000 Node.random 為空（null）或指向鏈表中的節(jié)點(diǎn)。節(jié)點(diǎn)數(shù)目不超過(guò) 1000 。

解題思路

哈希的做法，在大多數(shù)公司的面試官面前并不是一個(gè)滿(mǎn)意的答案，所以需要知道原地修改的解法才能夠從容面對(duì)面試。原地修改解法流程：假設(shè)三個(gè)節(jié)點(diǎn)初始如下

1.第一次遍歷，復(fù)制一個(gè)新的節(jié)點(diǎn)在原有節(jié)點(diǎn)之后，如 1 -> 2 -> 3 -> null 復(fù)制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null 第一次遍歷，構(gòu)建的節(jié)點(diǎn)，random還未連接起來(lái)，如下圖

我們需要把A指向C，因?yàn)槌跏嫉腁的random指針指向了C，那是不是有這樣的公式： A->random = A->random->next

2.第二次遍歷，從頭開(kāi)始遍歷鏈表，通過(guò) cur.next.random = cur.random.next 可以將復(fù)制節(jié)點(diǎn)的隨機(jī)指針串起來(lái)，當(dāng)然需要判斷 cur.random 是否存在

3.第三次遍歷，就比較簡(jiǎn)單了，只是找出這些相鄰節(jié)點(diǎn)，組成結(jié)果就可以

class Solution {
	public Node copyRandomList(Node head) {
		// if head == null,則return null
		if (head == null) {
			return null;
		}
		// 第一次遍歷， 1 -> `1` -> 2 -> `2` -> 3 - > `3` -> null
		Node cur = head;
		while (cur != null) {
			Node node = new Node(cur.val);
			Node temp = cur.next;
			cur.next = node;
			cur.next.next = temp;
			cur = cur.next.next;
		}
		// 第二次遍歷，填充random節(jié)點(diǎn)
		cur = head;
		while (cur != null) {
			Node newNode = cur.next;
			newNode.random = cur.random != null ? cur.random.next : null;
			cur = cur.next.next;
		}
		// 第三次遍歷，拆分
		Node headNew = head.next;
		for (Node node = head; node != null; node = node.next) {
			Node nodeNew = node.next;
			node.next = node.next.next;
			nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
		}
		return headNew;
	}
	class Node {
		int val;
		Node next;
		Node random;
		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}
	}
}

以上就是java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于java算法復(fù)雜鏈表復(fù)制的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: