반응형
인터뷰 질문 : 새 노드를 만들지 않고 정렬 된 두 개의 단일 연결 목록 병합
이것은 면접을위한 필기 시험 중에 묻는 프로그래밍 질문입니다. "이미 정렬 된 두 개의 단일 연결 목록이 있습니다.이를 병합하고 새 추가 노드를 생성하지 않고 새 목록의 헤드를 반환해야합니다. 반환 된 목록도 정렬되어야합니다."
메소드 서명은 다음과 같습니다. Node MergeLists (Node list1, Node list2);
노드 클래스는 다음과 같습니다.
class Node{
int data;
Node next;
}
나는 많은 솔루션을 시도했지만 여분의 노드 나사를 만들지 않았습니다. 도와주세요.
다음은 함께 제공되는 블로그 항목 http://techieme.in/merging-two-sorted-singly-linked-list/입니다.
Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.data < list2.data) {
list1.next = MergeLists(list1.next, list2);
return list1;
} else {
list2.next = MergeLists(list2.next, list1);
return list2;
}
}
새 노드 할당을 피하기 위해 재귀가 필요하지 않아야합니다.
Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
Node head;
if (list1.data < list2.data) {
head = list1;
} else {
head = list2;
list2 = list1;
list1 = head;
}
while(list1.next != null) {
if (list1.next.data > list2.data) {
Node tmp = list1.next;
list1.next = list2;
list2 = tmp;
}
list1 = list1.next;
}
list1.next = list2;
return head;
}
Node MergeLists(Node node1, Node node2)
{
if(node1 == null)
return node2;
else (node2 == null)
return node1;
Node head;
if(node1.data < node2.data)
{
head = node1;
node1 = node1.next;
else
{
head = node2;
node2 = node2.next;
}
Node current = head;
while((node1 != null) ||( node2 != null))
{
if (node1 == null) {
current.next = node2;
return head;
}
else if (node2 == null) {
current.next = node1;
return head;
}
if (node1.data < node2.data)
{
current.next = node1;
current = current.next;
node1 = node1.next;
}
else
{
current.next = node2;
current = current.next;
node2 = node2.next;
}
}
current.next = NULL // needed to complete the tail of the merged list
return head;
}
정렬 된 두 개의 연결 목록 A와 B를 병합하는 방법에 대한 알고리즘은 다음과 같습니다.
while A not empty or B not empty:
if first element of A < first element of B:
remove first element from A
insert element into C
end if
else:
remove first element from B
insert element into C
end while
여기서 C는 출력 목록입니다.
엄마, 재귀 없음!
struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;
for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
if (cmp(one,two) <=0) { *tail = one; one=one->next; }
else { *tail = two; two=two->next; }
}
*tail = one ? one: two;
return result;
}
반복은 아래와 같이 할 수 있습니다. 복잡성 = O (n)
public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
LLNode mergedNode ;
LLNode tempNode ;
if (nodeA == null) {
return nodeB;
}
if (nodeB == null) {
return nodeA;
}
if ( nodeA.getData() < nodeB.getData())
{
mergedNode = nodeA;
nodeA = nodeA.getNext();
}
else
{
mergedNode = nodeB;
nodeB = nodeB.getNext();
}
tempNode = mergedNode;
while (nodeA != null && nodeB != null)
{
if ( nodeA.getData() < nodeB.getData())
{
mergedNode.setNext(nodeA);
nodeA = nodeA.getNext();
}
else
{
mergedNode.setNext(nodeB);
nodeB = nodeB.getNext();
}
mergedNode = mergedNode.getNext();
}
if (nodeA != null)
{
mergedNode.setNext(nodeA);
}
if (nodeB != null)
{
mergedNode.setNext(nodeB);
}
return tempNode;
}
Node mergeList(Node h1, Node h2) {
if (h1 == null) return h2;
if (h2 == null) return h1;
Node head;
if (h1.data < h2.data) {
head = h1;
} else {
head = h2;
h2 = h1;
h1 = head;
}
while (h1.next != null && h2 != null) {
if (h1.next.data < h2.data) {
h1 = h1.next;
} else {
Node afterh2 = h2.next;
Node afterh1 = h1.next;
h1.next = h2;
h2.next = afterh1;
if (h2.next != null) {
h2 = afterh2;
}
}
}
return head;
}
이는 추가 노드를 생성하지 않고 다른 노드 참조가 매개 변수 (노드 임시)에 전달되는 방식으로 수행 될 수 있습니다.
private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
if(nodeList1.data <= nodeList2.data){
temp = nodeList1;
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
}
else{
temp = nodeList2;
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
}
return temp;
}
나는 해결책을 어떻게 생각했는지를 공유하고 싶습니다 ... 나는 재귀를 포함하는 해결책을 보았고 그것들은 꽤 놀랍습니다. 잘 기능적이고 모듈화 된 사고의 결과입니다. 공유해 주셔서 정말 감사합니다.
재귀가 큰 조명에서는 작동하지 않고 스택 호출이 오버플로된다는 점을 추가하고 싶습니다. 그래서 나는 반복적 인 접근 방식을 시도하기로 결정했습니다. 그리고 이것이 내가 얻은 것입니다.
코드는 꽤 자명하며이를 보장하기 위해 인라인 주석을 추가했습니다.
이해하지 못하는 경우 알려 주시면 가독성을 향상시킬 것입니다 (아마도 내 코드를 잘못 해석하고있을 수 있습니다).
import java.util.Random;
public class Solution {
public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {
T data;
Node next;
@Override
public int compareTo(Node<T> otherNode) {
return data.compareTo(otherNode.data);
}
@Override
public String toString() {
return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null");
}
}
public static Node merge(Node firstLeft, Node firstRight) {
combine(firstLeft, firstRight);
return Comparision.perform(firstLeft, firstRight).min;
}
private static void combine(Node leftNode, Node rightNode) {
while (leftNode != null && rightNode != null) {
// get comparision data about "current pair of nodes being analized".
Comparision comparision = Comparision.perform(leftNode, rightNode);
// stores references to the next nodes
Node nextLeft = leftNode.next;
Node nextRight = rightNode.next;
// set the "next node" of the "minor node" between the "current pair of nodes being analized"...
// ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision.
comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min;
if (comparision.min == leftNode) {
leftNode = nextLeft;
} else {
rightNode = nextRight;
}
}
}
/** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */
private static class Comparision {
private final Node min;
private final Node max;
private Comparision(Node min, Node max) {
this.min = min;
this.max = max;
}
private static Comparision perform(Node a, Node b) {
Node min, max;
if (a != null && b != null) {
int comparision = a.compareTo(b);
if (comparision <= 0) {
min = a;
max = b;
} else {
min = b;
max = a;
}
} else {
max = null;
min = (a != null) ? a : b;
}
return new Comparision(min, max);
}
}
// Test example....
public static void main(String args[]) {
Node firstLeft = buildList(20);
Node firstRight = buildList(40);
Node firstBoth = merge(firstLeft, firstRight);
System.out.println(firstBoth);
}
// someone need to write something like this i guess...
public static Node buildList(int size) {
Random r = new Random();
Node<Integer> first = new Node<>();
first.data = 0;
first.next = null;
Node<Integer> current = first;
Integer last = first.data;
for (int i = 1; i < size; i++) {
Node<Integer> node = new Node<>();
node.data = last + r.nextInt(5);
last = node.data;
node.next = null;
current.next = node;
current = node;
}
return first;
}
}
간단한 반복 솔루션.
Node* MergeLists(Node* A, Node* B)
{
//handling the corner cases
//if both lists are empty
if(!A && !B)
{
cout << "List is empty" << endl;
return 0;
}
//either of list is empty
else if(!A) return B;
else if(!B) return A;
else
{
Node* head = NULL;//this will be the head of the newList
Node* previous = NULL;//this will act as the
/* In this algorithm we will keep the
previous pointer that will point to the last node of the output list.
And, as given we have A & B as pointer to the given lists.
The algorithm will keep on going untill either one of the list become empty.
Inside of the while loop, it will divide the algorithm in two parts:
- First, if the head of the output list is not obtained yet
- Second, if head is already there then we will just compare the values and keep appending to the 'previous' pointer.
When one of the list become empty we will append the other 'left over' list to the output list.
*/
while(A && B)
{
if(!head)
{
if(A->data <= B->data)
{
head = A;//setting head of the output list to A
previous = A; //initializing previous
A = A->next;
}
else
{
head = B;//setting head of the output list to B
previous = B;//initializing previous
B = B->next;
}
}
else//when head is already set
{
if(A->data <= B->data)
{
if(previous->next != A)
previous->next = A;
A = A->next;//Moved A forward but keeping B at the same position
}
else
{
if(previous->next != B)
previous->next = B;
B = B->next; //Moved B forward but keeping A at the same position
}
previous = previous->next;//Moving the Output list pointer forward
}
}
//at the end either one of the list would finish
//and we have to append the other list to the output list
if(!A)
previous->next = B;
if(!B)
previous->next = A;
return head; //returning the head of the output list
}
}
반복적 인 솔루션을 아래에 보여줍니다. 재귀 솔루션은 더 간결하지만 목록의 길이를 모르기 때문에 재귀는 스택 오버플로의 위험이 있습니다.
기본 아이디어는 병합 정렬의 병합 단계와 유사합니다. 각 입력 목록에 해당하는 포인터를 유지합니다. 각 반복에서 더 작은 요소에 해당하는 포인터를 전진시킵니다. 그러나 대부분의 사람들이 걸려 넘어지는 한 가지 중요한 차이점이 있습니다. 병합 정렬에서는 결과 배열을 사용하므로 삽입 할 다음 위치는 항상 결과 배열의 인덱스입니다. 연결 목록의 경우 정렬 된 목록의 마지막 요소에 대한 포인터를 유지해야합니다. 포인터는 현재 반복에 대해 더 작은 요소가있는 항목에 따라 한 입력 목록에서 다른 입력 목록으로 이동할 수 있습니다.
이를 통해 다음 코드는 자명해야합니다.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode first = l1;
ListNode second = l2;
ListNode head = null;
ListNode last = null;
while (first != null && second != null) {
if (first.val < second.val) {
if (last != null) {
last.next = first;
}
last = first;
first = first.next;
} else {
if (last != null) {
last.next = second;
}
last = second;
second = second.next;
}
if (head == null) {
head = last;
}
}
if (first == null) {
last.next = second;
}
if (second == null) {
last.next = first;
}
return head;
}
우선 "새로운 추가 노드를 만들지 않고" 의 의미를 이해합니다. 내가 이해하기 때문에 기존 노드를 가리키는 포인터를 가질 수 없다는 의미는 아닙니다.
재귀를 사용하여 동일한 것을 달성하더라도 기존 노드에 대한 포인터를 말하지 않고는이를 달성 할 수 없으며, 시스템은 호출 스택으로 포인터를 생성합니다. 코드에서 피한 포인터를 추가하라고 시스템에 지시하는 것과 같습니다.
추가 포인터를 사용 하여 동일한 결과를 얻을 수있는 간단한 기능 :
typedef struct _LLNode{
int value;
struct _LLNode* next;
}LLNode;
LLNode* CombineSortedLists(LLNode* a,LLNode* b){
if(NULL == a){
return b;
}
if(NULL == b){
return a;
}
LLNode* root = NULL;
if(a->value < b->value){
root = a;
a = a->next;
}
else{
root = b;
b = b->next;
}
LLNode* curr = root;
while(1){
if(a->value < b->value){
curr->next = a;
curr = a;
a=a->next;
if(NULL == a){
curr->next = b;
break;
}
}
else{
curr->next = b;
curr = b;
b=b->next;
if(NULL == b){
curr->next = a;
break;
}
}
}
return root;
}
Node * merge_sort(Node *a, Node *b){
Node *result = NULL;
if(a == NULL)
return b;
else if(b == NULL)
return a;
/* For the first node, we would set the result to either a or b */
if(a->data <= b->data){
result = a;
/* Result's next will point to smaller one in lists
starting at a->next and b */
result->next = merge_sort(a->next,b);
}
else {
result = b;
/*Result's next will point to smaller one in lists
starting at a and b->next */
result->next = merge_sort(a,b->next);
}
return result;
}
http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html에 대한 내 블로그 게시물을 참조하십시오.
Node MergeLists(Node list1, Node list2) {
//if list is null return other list
if(list1 == null)
{
return list2;
}
else if(list2 == null)
{
return list1;
}
else
{
Node head;
//Take head pointer to the node which has smaller first data node
if(list1.data < list2.data)
{
head = list1;
list1 = list1.next;
}
else
{
head = list2;
list2 = list2.next;
}
Node current = head;
//loop till both list are not pointing to null
while(list1 != null || list2 != null)
{
//if list1 is null, point rest of list2 by current pointer
if(list1 == null){
current.next = list2;
return head;
}
//if list2 is null, point rest of list1 by current pointer
else if(list2 == null){
current.next = list1;
return head;
}
//compare if list1 node data is smaller than list2 node data, list1 node will be
//pointed by current pointer
else if(list1.data < list2.data)
{
current.next = list1;
current = current.next;
list1 = list1.next;
}
else
{
current.next = list2;
current = current.next;
list2 = list2.next;
}
}
return head;
}
}
다음은 java.util을 구현 한 연결 목록을 사용하는 완전한 작업 예제입니다. main () 메서드 안에 아래 코드를 복사하여 붙여 넣을 수 있습니다.
LinkedList<Integer> dList1 = new LinkedList<Integer>();
LinkedList<Integer> dList2 = new LinkedList<Integer>();
LinkedList<Integer> dListMerged = new LinkedList<Integer>();
dList1.addLast(1);
dList1.addLast(8);
dList1.addLast(12);
dList1.addLast(15);
dList1.addLast(85);
dList2.addLast(2);
dList2.addLast(3);
dList2.addLast(12);
dList2.addLast(24);
dList2.addLast(85);
dList2.addLast(185);
int i = 0;
int y = 0;
int dList1Size = dList1.size();
int dList2Size = dList2.size();
int list1Item = dList1.get(i);
int list2Item = dList2.get(y);
while (i < dList1Size || y < dList2Size) {
if (i < dList1Size) {
if (list1Item <= list2Item || y >= dList2Size) {
dListMerged.addLast(list1Item);
i++;
if (i < dList1Size) {
list1Item = dList1.get(i);
}
}
}
if (y < dList2Size) {
if (list2Item <= list1Item || i >= dList1Size) {
dListMerged.addLast(list2Item);
y++;
if (y < dList2Size) {
list2Item = dList2.get(y);
}
}
}
}
for(int x:dListMerged)
{
System.out.println(x);
}
재귀 방식 (스테판 답변의 변형)
MergeList(Node nodeA, Node nodeB ){
if(nodeA==null){return nodeB};
if(nodeB==null){return nodeA};
if(nodeB.data<nodeA.data){
Node returnNode = MergeNode(nodeA,nodeB.next);
nodeB.next = returnNode;
retturn nodeB;
}else{
Node returnNode = MergeNode(nodeA.next,nodeB);
nodeA.next=returnNode;
return nodeA;
}
이것을 시각화하려면 아래 링크 목록을 고려하십시오.
2>4목록 A 1>3목록 B
Stefan과 거의 같은 대답 (재귀 적이 지 않음)이지만 약간의 주석 / 의미있는 변수 이름이 있습니다. 누군가가 관심이 있다면 주석에 이중 연결 목록도 포함
예를 고려하십시오
5->10->15>21 // List1
2->3->6->20 //List2
Node MergeLists(List list1, List list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if(list1.head.data>list2.head.data){
listB =list2; // loop over this list as its head is smaller
listA =list1;
} else {
listA =list2; // loop over this list
listB =list1;
}
listB.currentNode=listB.head;
listA.currentNode=listA.head;
while(listB.currentNode!=null){
if(listB.currentNode.data<listA.currentNode.data){
Node insertFromNode = listB.currentNode.prev;
Node startingNode = listA.currentNode;
Node temp = inserFromNode.next;
inserFromNode.next = startingNode;
startingNode.next=temp;
startingNode.next.prev= startingNode; // for doubly linked list
startingNode.prev=inserFromNode; // for doubly linked list
listB.currentNode= listB.currentNode.next;
listA.currentNode= listA.currentNode.next;
}
else
{
listB.currentNode= listB.currentNode.next;
}
}
질문에 대한 나의 견해는 다음과 같습니다.
의사 코드 :
Compare the two heads A and B.
If A <= B, then add A and move the head of A to the next node.
Similarly, if B < A, then add B and move the head of B to the next node B.
If both A and B are NULL then stop and return.
If either of them is NULL, then traverse the non null head till it becomes NULL.
암호:
public Node mergeLists(Node headA, Node headB) {
Node merge = null;
// If we have reached the end, then stop.
while (headA != null || headB != null) {
// if B is null then keep appending A, else check if value of A is lesser or equal than B
if (headB == null || (headA != null && headA.data <= headB.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headA.data);
// Since A is <= B, Move head of A to next node
headA = headA.next;
// if A is null then keep appending B, else check if value of B is lesser than A
} else if (headA == null || (headB != null && headB.data < headA.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headB.data);
// Since B is < A, Move head of B to next node
headB = headB.next;
}
}
return merge;
}
public Node add(Node head, int data) {
Node end = new Node(data);
if (head == null) {
return end;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = end;
return head;
}
/* Simple/Elegant Iterative approach in Java*/
private static LinkedList mergeLists(LinkedList list1, LinkedList list2) {
Node head1 = list1.start;
Node head2 = list2.start;
if (list1.size == 0)
return list2;
if (list2.size == 0)
return list1;
LinkedList mergeList = new LinkedList();
while (head1 != null && head2 != null) {
if (head1.getData() < head2.getData()) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
} else {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
}
while (head1 != null) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
}
while (head2 != null) {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
return mergeList;
}
/* Build-In singly LinkedList class in Java*/
class LinkedList {
Node start;
int size = 0;
void insert(int data) {
if (start == null)
start = new Node(data);
else {
Node temp = start;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(new Node(data));
}
size++;
}
@Override
public String toString() {
String str = "";
Node temp=start;
while (temp != null) {
str += temp.getData() + "-->";
temp = temp.getNext();
}
return str;
}
}
LLNode *mergeSorted(LLNode *h1, LLNode *h2)
{
LLNode *h3=NULL;
LLNode *h3l;
if(h1==NULL && h2==NULL)
return NULL;
if(h1==NULL)
return h2;
if(h2==NULL)
return h1;
if(h1->data<h2->data)
{
h3=h1;
h1=h1->next;
}
else
{
h3=h2;
h2=h2->next;
}
LLNode *oh=h3;
while(h1!=NULL && h2!=NULL)
{
if(h1->data<h2->data)
{
h3->next=h1;
h3=h3->next;
h1=h1->next;
}
else
{
h3->next=h2;
h3=h3->next;
h2=h2->next;
}
}
if(h1==NULL)
h3->next=h2;
if(h2==NULL)
h3->next=h1;
return oh;
}
// Common code for insert at the end
private void insertEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
newNode.next = head;
head = tail = newNode;
return;
}
Node tempNode = tail;
tempNode.next = newNode;
tail = newNode;
}
private void mergerTwoSortedListInAscOrder(Node tempNode1, Node tempNode2) {
if (tempNode1 == null && tempNode2 == null)
return;
if (tempNode1 == null) {
head3 = tempNode2;
return;
}
if (tempNode2 == null) {
head3 = tempNode1;
return;
}
while (tempNode1 != null && tempNode2 != null) {
if (tempNode1.mData < tempNode2.mData) {
insertEndForHead3(tempNode1.mData);
tempNode1 = tempNode1.next;
} else if (tempNode1.mData > tempNode2.mData) {
insertEndForHead3(tempNode2.mData);
tempNode2 = tempNode2.next;
} else {
insertEndForHead3(tempNode1.mData);
insertEndForHead3(tempNode2.mData);
tempNode1 = tempNode1.next;
tempNode2 = tempNode2.next;
}
}
if (tempNode1 != null) {
while (tempNode1 != null) {
insertEndForHead3(tempNode1.mData);
tempNode1 = tempNode1.next;
}
}
if (tempNode2 != null) {
while (tempNode2 != null) {
insertEndForHead3(tempNode2.mData);
tempNode2 = tempNode2.next;
}
}
}
:) GlbMP
public static Node merge(Node h1, Node h2) {
Node h3 = new Node(0);
Node current = h3;
boolean isH1Left = false;
boolean isH2Left = false;
while (h1 != null || h2 != null) {
if (h1.data <= h2.data) {
current.next = h1;
h1 = h1.next;
} else {
current.next = h2;
h2 = h2.next;
}
current = current.next;
if (h2 == null && h1 != null) {
isH1Left = true;
break;
}
if (h1 == null && h2 != null) {
isH2Left = true;
break;
}
}
if (isH1Left) {
while (h1 != null) {
current.next = h1;
current = current.next;
h1 = h1.next;
}
}
if (isH2Left) {
while (h2 != null) {
current.next = h2;
current = current.next;
h2 = h2.next;
}
}
h3 = h3.next;
return h3;
}
많은 'if'조건을 저장하기 위해 처음에는 더미 노드를 하나만 만들었습니다.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode list1Cursor = l1;
ListNode list2Cursor = l2;
ListNode currentNode = new ListNode(-1); // Dummy node
ListNode head = currentNode;
while (list1Cursor != null && list2Cursor != null)
{
if (list1Cursor.val < list2Cursor.val) {
currentNode.next = list1Cursor;
list1Cursor = list1Cursor.next;
currentNode = currentNode.next;
} else {
currentNode.next = list2Cursor;
list2Cursor = list2Cursor.next;
currentNode = currentNode.next;
}
}
// Complete the rest
while (list1Cursor != null) {
currentNode.next = list1Cursor;
currentNode = currentNode.next;
list1Cursor = list1Cursor.next;
}
while (list2Cursor != null) {
currentNode.next = list2Cursor;
currentNode = currentNode.next;
list2Cursor = list2Cursor.next;
}
return head.next;
}
private static Node mergeLists(Node L1, Node L2) {
Node P1 = L1.val < L2.val ? L1 : L2;
Node P2 = L1.val < L2.val ? L2 : L1;
Node BigListHead = P1;
Node tempNode = null;
while (P1 != null && P2 != null) {
if (P1.next != null && P1.next.val >P2.val) {
tempNode = P1.next;
P1.next = P2;
P1 = P2;
P2 = tempNode;
} else if(P1.next != null)
P1 = P1.next;
else {
P1.next = P2;
break;
}
}
return BigListHead;
}
void printLL(){
NodeLL cur = head;
if(cur.getNext() == null){
System.out.println("LL is emplty");
}else{
//System.out.println("printing Node");
while(cur.getNext() != null){
cur = cur.getNext();
System.out.print(cur.getData()+ " ");
}
}
System.out.println();
}
void mergeSortedList(NodeLL node1, NodeLL node2){
NodeLL cur1 = node1.getNext();
NodeLL cur2 = node2.getNext();
NodeLL cur = head;
if(cur1 == null){
cur = node2;
}
if(cur2 == null){
cur = node1;
}
while(cur1 != null && cur2 != null){
if(cur1.getData() <= cur2.getData()){
cur.setNext(cur1);
cur1 = cur1.getNext();
}
else{
cur.setNext(cur2);
cur2 = cur2.getNext();
}
cur = cur.getNext();
}
while(cur1 != null){
cur.setNext(cur1);
cur1 = cur1.getNext();
cur = cur.getNext();
}
while(cur2 != null){
cur.setNext(cur2);
cur2 = cur2.getNext();
cur = cur.getNext();
}
printLL();
}
두 개의 정렬 된 연결 목록 headA와 headB를 병합하는 방법에 대한 코드는 다음과 같습니다.
Node* MergeLists1(Node *headA, Node* headB)
{
Node *p = headA;
Node *q = headB;
Node *result = NULL;
Node *pp = NULL;
Node *qq = NULL;
Node *head = NULL;
int value1 = 0;
int value2 = 0;
if((headA == NULL) && (headB == NULL))
{
return NULL;
}
if(headA==NULL)
{
return headB;
}
else if(headB==NULL)
{
return headA;
}
else
{
while((p != NULL) || (q != NULL))
{
if((p != NULL) && (q != NULL))
{
int value1 = p->data;
int value2 = q->data;
if(value1 <= value2)
{
pp = p->next;
p->next = NULL;
if(result == NULL)
{
head = result = p;
}
else
{
result->next = p;
result = p;
}
p = pp;
}
else
{
qq = q->next;
q->next = NULL;
if(result == NULL)
{
head = result = q;
}
else
{
result->next = q;
result = q;
}
q = qq;
}
}
else
{
if(p != NULL)
{
pp = p->next;
p->next = NULL;
result->next = p;
result = p;
p = pp;
}
if(q != NULL)
{
qq = q->next;
q->next = NULL;
result->next = q;
result = q;
q = qq;
}
}
}
}
return head;
}
반응형
'program story' 카테고리의 다른 글
| yii2에서 드롭 다운 목록을 만드는 방법은 무엇입니까? (0) | 2020.10.06 |
|---|---|
| Android에서 밀리 초를 날짜 형식으로 변환하는 방법은 무엇입니까? (0) | 2020.10.06 |
| Windows의 Node.js-콘솔을 지우는 방법 (0) | 2020.10.06 |
| 엔터프라이즈 iOS 애플리케이션을 설치할 때 "신뢰할 수없는 앱 개발자"메시지 (0) | 2020.10.06 |
| 2.3에서 Done SoftInput 작업 레이블이있는 여러 줄 EditText (0) | 2020.10.06 |