LeetCode 148 Sort List

nayu1105·2023년 9월 3일

leetcode 알고리즘

LeetCode

목록 보기

22/28

LeetCode 148 Sort List 풀러가기

문제

linked list의 head가 주어지면, 이 linkedlist를 sort하여 return 하면 된다.

문제 분석

sort 방법 중 시간복잡도 O(NlogN)인, merge sort로 구현하려 했다.

merge sort (병합정렬)

merge sort는 list를 모두 나눈후, 길이가 1이 되엇을 때 각 노드끼리 합치면서 sort하는 개념이다.

저장 공간 길이가 1일 될때까지 분할

나눠진 노드들을 병합하며 min 값부터 저장
최종 노드 list가 1개 될 때가지 이 과정을 반복

첫번째 시도

merge sort 순서가 계속해서 나누다가 길이가 1일때 merge 하는 것이니, 재귀함수로 구현하면 될 것 같았다.

head를 기준으로 절반을 나누어서 계속해서 나누며 재귀함수를 불렀다.

만약 head.next가 null 이면 길이가 1이니, 리턴하고, merge 하는 식으로 짰다.

구현하다가 head를 기준으로 절반을 나누는부분은 다른분의 코드를 보며 도움을 받았다.

다른 분은 slow, fast를 써서, fast가 slow 보다 두배로 빠르게 해서, 끝에 도달하도록 했다.

끝에 도달하면 while문을 종료하고, slow의 next를 null 로 만들어, 두 list를 분리했다.

코드

class Solution {
    public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    ListNode prev = null, slow = head, fast = head;
    
    // 도움받은 부분
    while (fast != null && fast.next != null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
    prev.next = null;
    
    
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    return merge(l1, l2);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode list = new ListNode(0);
    ListNode temp = list;
    
    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 list.next;
  }
}