[Leetcode Top Interview 150] 148. Sort List

난이도 : medium

문제링크

• 링크드리스트의 head가 주어짐
• 오름차순으로 정렬된 링크드리스트 참조객체를 리턴하라
• node 갯수 : [0, 5 * 104]
• -105 <= Node.val <= 105

 

1. 접근법

• 시간복잡도를 줄일 수 있는 병합정렬을 이용하여 정렬 수행
  • 주어진 링크드리스트를 반으로 자름
  • 정렬 및 병합

 

2. 의사코드

// 재귀함수 구현을 위한 종료조건 작성
if (head == null || head.next == null) {
  return head;
}

// 현재 head가 가리키는 링크드리스트에서 중간에 위치한 노드를 리턴
// 해당 중간노드와 이전 노드의 연결을 끊어줌
ListNode mid = getMid(head);

// head와 mid를 대상으로 재귀적으로 호출하여 정렬함
ListNode left = sortList(head);
ListNode right = sortList(mid);

// 반씩 잘려진 링크드리스트를 다시 오름차순으로 병합하고 리턴함
return merage(left, right);

 

3. 구현 코드

public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = getMid(head);

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        return merge(left, right);
    }

    private ListNode getMid(ListNode head) {
        ListNode temp = head;
        int count = 0;
        while (temp.next != null) {
            temp = temp.next;
            count++;
        }

        temp = head;
        ListNode before = head;
        count = (count/2) + (count%2);
        while (count > 0) {
            before = temp;
            temp = temp.next;
            count--;
        }

        before.next = null;

        return temp;
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode current = dummy;

        while (a != null && b != null) {
            if (a.val < b.val) {
                dummy.next = new ListNode(a.val);
                a = a.next;
            } else if (b.val < a.val) {
                dummy.next = new ListNode(b.val);
                b = b.next;
            } else {
                dummy.next = new ListNode(a.val, new ListNode(a.val));
                dummy = dummy.next;
                a = a.next;
                b = b.next;
            }

            dummy = dummy.next;
        }

        if (a != null) {
            dummy.next = a;
        }

        if (b != null) {
            dummy.next = b;
        }

        return current.next;
    }

• 노드의 중간 노드를 가져오기 위해서 중간 노드의 위치를 찾음
  • 찾은 노드의 직전 노드의 next를 null로 하여 연결을 끊어줌
• left, right 노드를 오름차순으로 병합함
  • 중복 값의 노드도 포함시켜서 처리함

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(nlogn) - 분할 * (정렬 +  mid 노드 찾기)
  • 노드 분할 : O(logn)
  • 정렬 +  mid 노드 찾기 : 각각 O(n)
• 공간복잡도 : O(n) - 링크드리스트 길이만큼 새로운 링크드리스트를 생성함

 

5. 개선점

• 중간 노드를 찾는 부분을 투포인터를 사용하여 연산 횟수를 줄였음

private ListNode getMid(ListNode 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;
    
    return slow;
}

 

6. 회고

다른 블로그나 유튜브에서도 동일하게 풀었다

slow, fast는 linkedlist에서 자주 쓰이는 투포인터 패턴이니 기억하자. 부족한점이니 숙지하기

(이해는 했지만 한두문제 풀어본게 다라.. 반복문을 돌리게 된다)