문제
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
주어진 두 연결 리스트(Linked List)를 합쳐서 정렬된 하나의 리스트로 만들어라.
예시
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: l1 = [], l2 = [0]
Output: [0]
Input: l1 = [], l2 = []
Output: []답안
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
var node = new ListNode(0); // 초기화
var head = node;
while(l1 != null || l2 != null){
if(l2 == null || (l1 != null && l1.val <= l2.val)){
node.next = l1; // node가 l1를 향하도록
l1 = l1.next; // l1이 다음 위치로 이동
}
else{
node.next = l2; // node가 l2를 향하도록
l2 = l2.next; // l2가 다음 위치로 이동
}
node = node.next; // 다음 노드로 이동
}
return head.next; // l1,l2 둘 다 null일 경우 head.next로 빈 리스트 반환
}
}최상단에 정의된 ListNode 클래스를 참조하여 Solution 클래스에 코드를 작성한다.
연결 리스트(Linked List) 개념을 활용해 접근해야 한다.
연결 리스트는 데이터가 한쪽 방향으로만 연결되어 있다. 데이터가 저장된 객체를 node, 가장 첫번째 node를 head라고 부른다. 각 node는 데이터칸과 주소칸 두 개로 이루어져 있다. 데이터칸에는 현재 인덱스의 데이터를 저장하고, 주소칸에는 다음 인덱스의 주소를 저장하고 있다.
var node = new ListNode(0) : ListNode 클래스의 인스턴스 생성. 변수 node의 값을 0으로 한다.
var head = node : node의 값을 변수 head에 대입한다. head의 값은 0이 된다.
l1 = 1 - 3 - 8 - 10
l2 = 1 - 4 - 5 - 6
이라고 가정해보자.
if(l2 == null || (l1 != null && l1.val <= l2.val)){
node.next = l1; // node가 l1를 향하도록
l1 = l1.next; // l1이 다음 위치로 이동
}
else{
node.next = l2; // node가 l2를 향하도록
l2 = l2.next; // l2가 다음 위치로 이동
}
node = node.next;l1과 l2의 노드값을 비교하여 둘 중 작은 값의 노드를 선택하여 해당 노드가 다음 노드로 이동하도록 한다.
그리고 node를 다음 위치고 이동시키는 것을 반복하여 작은 값부터 차례대로 노드를 연결시킨다.