Geeksforgeeks - InsertSortedList

이미 정렬된 LinkedList에, 정렬을 유지한 채로 값을 넣는 문제다.

Example 1:

Input:
LinkedList: 25->36->47->58->69->80
data: 19
Output: 19 25 36 47 58 69 80

Example 2:

Input:
LinkedList: 50->100
data: 75
Output: 50 75 100

총 경우의 수는 3개이다.

1. new node가 head node가 되는 경우

1. head 노드가 null인 경우

현재 연결 리스트에 노드가 한 개도 없는 상태이므로, key값을 이용해 새로운 노드를 만든 후 head노드로 만들어준다.

2. 리스트에 넣을 key값이 head 노드의 값보다 작을 경우

head 노드가 null인 경우와 같이, 새롭게 만든 node가 head node가 되면 된다. 다만 이 경우에는 new_node.next가 head가 되어야 한다.

어차피 head 노드가 null인 경우 new_node.next에 head node를 넣을 때 null이 들어가므로, 위와 같은 if문으로 묶어줘도 잘 작동한다.

 

2. 리스트에 넣을 key값이 중간에 들어가거나, 가장 마지막에 들어가는 경우

node.next.data가 key값보다 큰 node 위치를 찾아야한다.

new_node.next가 node.next가 되면 되고, 그 후 node.next가 new_node가 되면 된다.

 

전체 코드

class InsertSortedList {
    Node sortedInsert(Node head1, int key) {
        Node new_node = new Node(key);
        Node current;
        if (head1 == null || head1.data > new_node.data) {
            new_node.next = head1;
            head1 = new_node;
        } else {
            current = head1;
            while (current.next != null && current.next.data < key) {
                current = current.next;
            }
            new_node.next = current.next;
            current.next = new_node;
        }
        return head1;
    }
}