📒

[LeetCode Top 150] 04-1. Sort List

상태

완료

수업

Algorithm Solving

주제

LeetCode Top Interview 150

4 more properties

참고

문제해설

NOTE

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150

문제 링크

•

입력 값 : 연결리스트 head

•

출력 값 : 연결리스트를 오름차순으로 정렬한 값

문제 로직고민

NOTE

/**
 * 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; }
 * }
 */
Java
복사
주어진 연결리스트 형식

•

병합정렬을 통해서 정렬한다!

◦

배열의 크기를 절반으로 나눈다. 

▪

순환확인에 사용했던 사이드 검출 알고리즘 사용(slow, fast)

▪

단 여기서 절반을 진행해야하므로, 시작 ~slow, slow.next ~ 끝으로 나눈다.

◦

병합정렬을 통해 2개의 연결 리스트를 정렬한다.

작성코드

NOTE

class Solution {
    public ListNode sortList(ListNode head) {

        if(head == null || head.next == null) return head;

        ListNode prev = null;
        ListNode slow = head;
        ListNode 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 l = new ListNode(0);
        ListNode p = l;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }
            else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if(l1 != null) p.next = l1;
        else if(l2 != null) p.next = l2;

        return l.next;
    }
}
Java
복사

정답코드

NOTE

class Solution {
    public ListNode sortList (ListNode head) {
        ListNode ans = mergeSort(head);
        System.gc();
        return ans;
    }

		// 중앙값 찾기
    static 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;
    }

    // 병합정렬 중앙값을 찾고 쪼갠다.
    static ListNode mergeSort(ListNode head)
    {
        // add your code here
        if(head==null || head.next==null)   return head;
        
     ListNode mid = findMid(head);
        
     ListNode head2 = mid.next;
        mid.next=null;
        
        head=mergeSort(head);
        head2=mergeSort(head2);
        
     ListNode ans = merge(head, head2);
        return ans;
        
    }
    
		// 병합정렬 진행
    static ListNode merge(ListNode head1, ListNode head2){
     ListNode newHead = new ListNode(-1);
     ListNode tmp=newHead;
        while(head1!=null && head2!=null){
            if(head1.val<=head2.val){
                tmp.next=head1;
                head1=head1.next;
            }else{
                tmp.next=head2;
                head2=head2.next;
            }
            tmp=tmp.next;
        }
        if(head1!=null) tmp.next=head1;
        if(head2!=null) tmp.next=head2;
        return newHead.next;
    }
}
Java
복사
메모리를 가장 적게 사용하는 코드

•

메모리가 상당히 낮게 나와서 코드를 최선의 코드를 읽어 보았는데 크게 찾이가 없는거 같다.

•

List에 모두 담은다음 정렬하고 다시 연결리스트에 값을 다 뿌려주는게 상당히 효율적으로 나왔는데 좀 당황스러웠다.