Leetcode Java Sort List

문제

Link

코드

/**
 * 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 sortList(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode prev = null;
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
      prev = slow;
      fast = fast.next.next;
      slow = slow.next;
    }
    prev.next = null;
    return this.merge(this.sortList(head), this.sortList(slow));
  }

  private ListNode merge(ListNode l1, ListNode l2) {
    ListNode listNode = new ListNode();
    ListNode temp = listNode;
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        temp.next = l1;
        l1 = l1.next;
      } else {
        temp.next = l2;
        l2 = l2.next;
      }
      temp = temp.next;
    }
    if (l1 != null) {
      temp.next = l1;
    }
    if (l2 != null) {
      temp.next = l2;
    }
    return listNode.next;
  }

}

결과

Link

설명

1. 주어진 ListNode인 head를 이용하여 오름차순으로 정렬하는 문제이다.

2. 주어진 ListNode인 head가 null이거나, head.next가 null인 경우 head를 반환한다.

3. 문제 풀이에 필요한 변수들은 정의한다.
   • prev는 slow의 이전 node를 저장할 ListNode로, null로 초기화 한다.
   • fast와 slow는 head의 중앙 지점을 찾을 ListNode로, 각각 head로 초기화 한다.

4. fast와 fast.next가 null이 아닐 때 까지 반복하여 prev에 slow를 저장하고, fast는 다다음 ListNode로, slow는 다음 ListNode로 이동시킨다.

5. 반복이 종료되면 prev.next에 null을 넣어 중앙을 기준으로 앞 부분은 slow에, 뒷 부분은 head에 저장되도록 연결을 끊어준다.

6. head와 slow를 재귀 호출을 이용하여 수행한 결과를 합쳐서 주어진 문제의 결과로 반환한다.
   • 결과를 저장할 listNode 변수를 정의하고, 임시 변수로 사용할 temp에도 listNode를 넣어준다.
   • l1과 l2가 null이 아닐 때 까지 반복하여 l1과 l2의 val 값이 작은 순서대로 temp.next에 넣어주고, 사용한 ListNode를 다음 값으로 넘겨주고 temp를 temp.next로 이동시킨다.
   • 반복문이 종료된 이후 l1 혹은 l2가 null이 아니면, temp.next에 해당 ListNode를 넣어 이어주고 listNode.next를 반환시킨다.

소스

Sample Code는 여기에서 확인 가능합니다.