題鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
分三步：
（1）復制每一個節點，使得復制后的節點都在當前節點的下一個節點
（2）原生鏈表的節點的指向任意節點，使復制的節點也都指向某一任意節點
（3）重新連接節點，把原生節點重新連接起來，把克隆后的節點連接起來
寫鏈表的題，盡量把鏈表結構和迭代程序畫出來，可以清晰的看出迭代程序，也更容易找出錯誤，
/**
* // Definition for a Node.
* function Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
if (head == null) {
return null;
}
//克隆節點
let tempHead = head;
while (tempHead != null) {
let cloneNode = new Node(tempHead.val);
let temp = tempHead.next;
tempHead.next = cloneNode;
cloneNode.next = temp;
tempHead = cloneNode.next;
}
//克隆Random指標
tempHead = head;
while (tempHead != null) {
let cloneNode = tempHead.next;
if (tempHead.random != null) {
let temp = tempHead.random;
cloneNode.random = temp.next;
}
tempHead = cloneNode.next;
}
//將克隆節點連接起來
let tempNode = head.next;
let resNode = tempNode;
head.next = tempNode.next;
head = head.next;
while (head != null) {
tempNode.next = head.next;
head.next = head.next.next;
tempNode = tempNode.next;
head = head.next;
}
return resNode;
};假設鏈表長度為n：
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/155449.html
標籤：其他
上一篇：el-table中常用用法的總結
下一篇：同一個tomcat服務器同一個埠部署多個專案可以做到嗎？網上眾口不一，有的說可以有的說不行，請教一下大家怎么解決