Sort List

LeetCode 148. Sort List

원문

Given the head of a linked list, return the list after sorting it in ascending order.

연결 리스트와 병합 정렬

여기를 참고했다.

분할정복으로 쪼개고 비교하고 병합하고를 반복하는 거야 알겠지만 연결리스트에서 어떻게 중간을 찾는지 몰라 찾아보니 Linked List Cycle에서 언급했던 플로이드의 토끼와 거북이 알고리즘을 사용하면 된다고 한다.

사이클 유무를 찾는데 사용한다더니 중간지점을 어떻게 찾는건가 싶어 찾아보니 이런 글을 발견했다.

간단히 말하자면, slow보다 fast가 두 배 빠르게 진행하기 때문에 fast가 끝에 도달했을 때에는 slow가 중간 지점에 있을 수밖에 없다는 이야기다.

코드

Python

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head

        mid = self.findMid(head)
        head2 = mid.next
        mid.next = None
        newHead1 = self.sortList(head)
        newHead2 = self.sortList(head2)
        final = self.merge(newHead1, newHead2)

        return final


    def findMid(self, head):
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow


    def merge(self, head1, head2):
        result = ListNode(-1)
        temp = result

        while head1 and head2:
            if head1.val < head2.val:
                temp.next = head1
                head1 = head1.next
            else:
                temp.next = head2
                head2 = head2.next
            temp = temp.next

        if head1: temp.next = head1
        if head2: temp.next = head2

        return result.next

Java

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

        ListNode mid = findMid(head);
        ListNode head2 = mid.next;
        mid.next = null;
        ListNode newHead1 = sortList(head);
        ListNode newHead2 = sortList(head2);

        return merge(newHead1, newHead2);
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode result = new ListNode(-1);
        ListNode temp = result;

        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;
            } else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }

        if (head1 != null) {
            temp.next = head1;
        }
        if (head2 != null) {
            temp.next = head2;
        }

        return result.next;
    }
}