여기에 추가로 연결된 목록이 주어지면 다음 각 노드에는 포인터가 있습니다. 어린이 별도의 목록을 가리킬 수도 있고 가리키지 않을 수도 있는 포인터입니다. 이러한 하위 목록에는 하나 이상 자신의 아이들이 생산하는 다단계 연결리스트. 주어진 머리 ~의 첫 번째 수준 목록의. 과제는 단조롭게 하다 모든 노드가 단일 레벨 연결리스트. 모든 노드가 해당 목록에 포함되도록 목록을 평면화합니다. 와야 해 첫 번째 그런 다음 노드의 두번째 수준 등등.
예:
입력:
Java에서 문자열을 정수로 변환하는 방법
int에서 char로 자바산출: 1->4->6->2->5->7->3->8
설명: 다중 레벨 연결 리스트는 하위 포인터가 없으므로 평면화됩니다.
우리는 논의했습니다 다중 레벨 연결 리스트의 평면화 여기서 노드에는 아래쪽과 다음 두 개의 포인터가 있습니다. 이전 포스팅에서 우리는 단조롭게 하는 연결리스트 레벨별로. 항상 처리해야 할 때 연결 목록을 평면화하는 방법 아래쪽 포인터 모든 노드에서 다음 전에.
목차
[예상 접근 방식] 재귀를 활용 - O(n) 시간과 O(n) 공간
C++접근 방식은 재귀적으로 납작하게 하다 다단계 연결 각 노드와 그 하위 노드를 순회하여 나열합니다. 첫 번째 하위 목록을 평면화 재귀를 사용합니다. 하위 목록이 평면화되면 다음 노드 in the sequence. 순회하는 동안 참조 에 이전에 방문한 노드 그리고 이를 현재 노드에 연결합니다. 이 프로세스는 서로 다른 수준의 모든 노드가 하나의 방식으로 연결되도록 보장합니다. 단일 선형 목록 보존하면서 깊이 순서.
김프를 jpg로 내보내기
// A C++ program to flatten a multi- // linked list depth-wise #include
// A Java program to flatten a multi- // linked list depth-wise class Node { int data; Node next down; Node(int x) { data = x; next = down = null; } } class GfG { static void flattenList(Node curr Node[] prev) { if (curr == null) return; // Add the current element to the list. if (prev[0] != null) prev[0].next = curr; prev[0] = curr; // Store the next pointer Node next = curr.next; // Recursively add the bottom list flattenList(curr.down prev); // Recursively add the next list flattenList(next prev); } static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + ' '); curr = curr.next; } System.out.println(); } public static void main(String[] args) { // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 Node head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); Node[] prev = new Node[1]; flattenList(head prev); printList(head); } }
# A Python program to flatten a multi- # linked list depth-wise class Node: def __init__(self x): self.data = x self.next = None self.down = None def flatten_list(curr prev): if curr is None: return # Add the current element to the list. if prev[0] is not None: prev[0].next = curr prev[0] = curr # Store the next pointer next_node = curr.next # Recursively add the bottom list flatten_list(curr.down prev) # Recursively add the next list flatten_list(next_node prev) def print_list(head): curr = head while curr is not None: print(curr.data end=' ') curr = curr.next print() if __name__ == '__main__': # Create a hard coded multi-linked list. # 5 -> 10 -> 19 -> 28 # | | # 7 22 # | | # 8 50 # | # 30 head = Node(5) head.down = Node(7) head.down.down = Node(8) head.down.down.down = Node(30) head.next = Node(10) head.next.next = Node(19) head.next.next.down = Node(22) head.next.next.down.down = Node(50) head.next.next.next = Node(28) prev = [None] flatten_list(head prev) print_list(head)
// A C# program to flatten a multi- // linked list depth-wise using System; class Node { public int data; public Node next down; public Node(int x) { data = x; next = down = null; } } class GfG { static void FlattenList(Node curr ref Node prev) { if (curr == null) return; // Add the current element to the list. if (prev != null) prev.next = curr; prev = curr; // Store the next pointer Node next = curr.next; // Recursively add the bottom list FlattenList(curr.down ref prev); // Recursively add the next list FlattenList(next ref prev); } static void PrintList(Node head) { Node curr = head; while (curr != null) { Console.Write(curr.data + ' '); curr = curr.next; } Console.WriteLine(); } static void Main(string[] args) { // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 Node head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); Node prev = null; FlattenList(head ref prev); PrintList(head); } }
// A Javascript program to flatten a multi- // linked list depth-wise class Node { constructor(x) { this.data = x; this.next = null; this.down = null; } } function flattenList(curr prev) { if (curr === null) return; // Add the current element to the list. if (prev[0] !== null) prev[0].next = curr; prev[0] = curr; // Store the next pointer let next = curr.next; // Recursively add the bottom list flattenList(curr.down prev); // Recursively add the next list flattenList(next prev); } function printList(head) { let curr = head; while (curr !== null) { console.log(curr.data); curr = curr.next; } } // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 let head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); let prev = [null]; flattenList(head prev); printList(head);
산출
5 7 8 30 10 19 22 50 28
[대체 접근 방식] 스택 사용 - O(n) 시간 및 O(n) 공간
C++접근 방식은 다음과 같습니다. 다단계 연결리스트 사용하여 스택 . 시작 미는 그만큼 헤드 노드 스택에. 그럼 동안 스택이 비어 있지 않습니다 팝 최상위 노드를 가져와 처리합니다. 각 노드에 대해 푸시 그것은 다음 및 아래쪽 포인터 (존재하는 경우) 스택에 추가합니다. 이 과정에서 현재 노드를 이전 노드에 연결 목록을 평평한 형태로 유지합니다. 순회는 모든 수준의 노드가 단일 수준 연결 목록 깊이 순서를 유지합니다.
// A C++ program to flatten a multi- // linked list depth-wise using stack #include
// A Java program to flatten a multi- // linked list depth-wise using stack import java.util.Stack; class Node { int data; Node next down; Node(int x) { data = x; next = down = null; } } class GfG { static void flattenList(Node head) { if (head == null) return; Stack<Node> stack = new Stack<>(); stack.push(head); Node prev = null; while (!stack.isEmpty()) { Node curr = stack.pop(); // Push the next node first if (curr.next != null) stack.push(curr.next); // Push the bottom node into stack if (curr.down != null) stack.push(curr.down); // Add the current element to the list if (prev != null) prev.next = curr; prev = curr; } } static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + ' '); curr = curr.next; } System.out.println(); } public static void main(String[] args) { // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 Node head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); flattenList(head); printList(head); } }
# A Python program to flatten a multi- # linked list depth-wise using stack class Node: def __init__(self x): self.data = x self.next = None self.down = None def flatten_list(head): if head is None: return stack = [head] prev = None while stack: curr = stack.pop() # Push the next node first if curr.next: stack.append(curr.next) # Push the bottom node into stack if curr.down: stack.append(curr.down) # Add the current element to the list if prev: prev.next = curr prev = curr def print_list(head): curr = head while curr: print(curr.data end=' ') curr = curr.next print() if __name__ == '__main__': # Create a hard coded multi-linked list. # 5 -> 10 -> 19 -> 28 # | | # 7 22 # | | # 8 50 # | # 30 head = Node(5) head.down = Node(7) head.down.down = Node(8) head.down.down.down = Node(30) head.next = Node(10) head.next.next = Node(19) head.next.next.down = Node(22) head.next.next.down.down = Node(50) head.next.next.next = Node(28) flatten_list(head) print_list(head)
// A C# program to flatten a multi- // linked list depth-wise using stack using System; using System.Collections.Generic; class Node { public int data; public Node next down; public Node(int x) { data = x; next = down = null; } } class GfG { static void FlattenList(Node head) { if (head == null) return; Stack<Node> stack = new Stack<Node>(); stack.Push(head); Node prev = null; while (stack.Count > 0) { Node curr = stack.Pop(); // Push the next node first if (curr.next != null) stack.Push(curr.next); // Push the bottom node into stack if (curr.down != null) stack.Push(curr.down); // Add the current element to the list if (prev != null) prev.next = curr; prev = curr; } } static void PrintList(Node head) { Node curr = head; while (curr != null) { Console.Write(curr.data + ' '); curr = curr.next; } Console.WriteLine(); } static void Main(string[] args) { // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 Node head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); FlattenList(head); PrintList(head); } }
// A Javascript program to flatten a multi- // linked list depth-wise using stack class Node { constructor(x) { this.data = x; this.next = null; this.down = null; } } function flattenList(head) { if (head === null) return; let stack = [head]; let prev = null; while (stack.length > 0) { let curr = stack.pop(); // Push the next node first if (curr.next !== null) stack.push(curr.next); // Push the bottom node into stack if (curr.down !== null) stack.push(curr.down); // Add the current element to the list if (prev !== null) prev.next = curr; prev = curr; } } function printList(head) { let curr = head; while (curr !== null) { console.log(curr.data); curr = curr.next; } } // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 let head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); flattenList(head); printList(head);
산출
5 7 8 30 10 19 22 50 28