자바 복잡 한 링크 복사 실현
4182 단어 검지 offer 알고리즘검지 offer 알고리즘(Java)
코드
static class ListNode {
int val;
ListNode next;
ListNode other;
public ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
", next=" + (next == null ? "null" : next.val) +
", other=" + (other == null ? "null" : other.val) +
"}";
}
}
/**
*
* a->b->c
* a->a1->b->b1->c->c1
* @param head
*/
private static void copy(ListNode head) {
ListNode listNode = head;
while (listNode != null) {
//
ListNode copy = new ListNode(listNode.val);
copy.next = listNode.next;
// next , next next
// a->b, a->a1->b
listNode.next = copy;
// ,
listNode = copy.next;
}
}
/**
* other
* @param head
*/
private static void setOther(ListNode head) {
ListNode listNode = head;
// listNode ,copy ,
while (listNode != null) {
//
ListNode copy = listNode.next;
// other null , other other next
// a -> a1 -> b -> b1 a1 a ,b1 b
// | ↑ a.other b,b.next b1( )
// |_ _ _ _ _ | a1 other a.other b next, a.other.next
if (listNode.other != null) {
copy.other = listNode.other.next;
}
// , next ,
listNode = copy.next;
}
}
/**
*
* @param head
* @return
*/
private static ListNode disConnect(ListNode head) {
ListNode listNode = head;
ListNode copyHead = null;
ListNode copyNode = null;
if (listNode != null) {
// next ( )
copyHead = listNode.next;
//
copyNode = listNode.next;
// next next( next)
listNode.next = copyNode.next;
// ,
listNode = listNode.next;
}
while (listNode != null) {
// next next
// a -> a1 -> b -> b1, a1 -> b1
copyNode.next = listNode.next;
//
copyNode = copyNode.next;
// next next( next)
// a -> a1 -> b -> b1, a -> b
listNode.next = copyNode.next;
// ,
listNode = listNode.next;
}
return copyHead;
}
public static ListNode cloneNode(ListNode head) {
if (head == null) {
return null;
}
copy(head);
setOther(head);
return disConnect(head);
}
public static void main(String[] args) {
ListNode root = bulidList();
ListNode copy = cloneNode(root);
while (root != null) {
System.out.println(root.toString());
root = root.next;
}
while (copy != null) {
System.out.println(copy.toString());
copy = copy.next;
}
}
private static ListNode bulidList() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node1.other = node3;
node4.other = node1;
return node1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
스 택 의 데이터 구 조 를 정의 합 니 다. 이 형식 에서 스 택 에 포 함 된 최소 요 소 를 얻 을 수 있 는 min 함수 (시간 복잡 도 는 O (1) 를 실현 하 십시오.package com.fiberhome.monitor.task; import java.util.Stack; public class SolutionStack { private Stack stack = new Stack...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.