검지 Offer16 - 두 정렬된 체인 테이블 결합
8610 단어 검지 Offer 문제 풀기
제목 설명
두 개의 단조롭고 점차적으로 증가하는 체인표를 입력하고 두 개의 체인표가 합성된 체인표를 출력한다. 물론 우리는 합성된 체인표가 단조롭고 줄지 않는 규칙을 만족시켜야 한다.
문제 풀이 사고방식
반복과 반복 두 가지 사고방식:
반복과 반복 두 가지 사고방식:
코드 구현 import java.util.Scanner;
public class Problem16 {
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public static ListNode Merge(ListNode l1,ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = Merge(l1.next, l2);
} else {
head = l2;
head.next = Merge(l1, l2.next);
}
return head;
}
public static ListNode Merge1(ListNode l1,ListNode l2) {
ListNode head = new ListNode(-1);
head.next = null;
ListNode root = head;
while(l1 != null && l2 != null) {
if(l1.val < l2.val){
head.next = l1;
head = l1;
l1 = l1.next;
}
else {
head.next = l2;
head = l2;
l2 = l2.next;
}
}
// , , 。
if(l1 != null) {
head.next = l1;
}
if(l2 != null) {
head.next = l2;
}
return root.next;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
}
}
import java.util.Scanner;
public class Problem16 {
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public static ListNode Merge(ListNode l1,ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = Merge(l1.next, l2);
} else {
head = l2;
head.next = Merge(l1, l2.next);
}
return head;
}
public static ListNode Merge1(ListNode l1,ListNode l2) {
ListNode head = new ListNode(-1);
head.next = null;
ListNode root = head;
while(l1 != null && l2 != null) {
if(l1.val < l2.val){
head.next = l1;
head = l1;
l1 = l1.next;
}
else {
head.next = l2;
head = l2;
l2 = l2.next;
}
}
// , , 。
if(l1 != null) {
head.next = l1;
}
if(l2 != null) {
head.next = l2;
}
return root.next;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
}
}