[leetcode] Sort List [21-03-25 수정완료]

풀이

arr에 해당 linkedlist를 받고 arr를 정렬하여, 다시 linkedlist의 value값을 arr에 있는 값으로 순차적으로 바꾼다.

유의할점

follow up(constant space)을 만족하려면 merge sort를 이용해서 풀수있다. 코드를 꼭 다시 공부하고 혼자 짜보자.

수정)
첫번째 Java 코드에서 list를 두개로 분할하는 방법추가 -> 어렵다.
constant space는 이해했지만 다음에 짜보기

코드

C++ : 내가 짠 코드 time : O(NlgN) , space : O(N).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector <int> arr;
        ListNode *tmp = head;
        while(tmp!=nullptr){
            arr.push_back(tmp->val);
            tmp = tmp->next;
        }
        sort(arr.begin(),arr.end());
        tmp = head;
        int cnt = 0;
        while(tmp!=nullptr){
            tmp->val = arr[cnt++]; 
            tmp = tmp-> next;
        }
        return head;
    }
};

C++ : 내가 짠 코드 time : O(NlogN) , space : O(logN)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //List를 두개로 쪼개어 정렬 한뒤 merge한다.
    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* left = sortList(head);
        ListNode* right = sortList(slow);
        return mergeSortList(left, right);
    }
    
    //두개의 List를 merge한 값을 반환한다.
    ListNode* mergeSortList(ListNode* l1, ListNode* l2){
        ListNode* dummy = new ListNode(0);
        ListNode* head = dummy;
        while(l1!=NULL&&l2!=NULL){
            if(l1->val < l2->val){
                head->next = l1;
                l1 = l1->next; 
            }else{
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next;
        }
        if(l1!=NULL) head->next = l1;
        if(l2!=NULL) head->next = l2;
        return dummy->next;
    }
};

Java : time : O(NlogN) , space : O(logN)

public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // step 1. cut the list to two halves
    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;
    
    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. merge l1 and l2
    return merge(l1, l2);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode l = new ListNode(0), 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;
    
    if (l2 != null)
      p.next = l2;
    
    return l.next;
  }

}

Java : time : O(NlogN) , space : constant space

/**
 * Merge sort use bottom-up policy, 
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
	ListNode *sortList(ListNode *head) {
		if(!head || !(head->next)) return head;
		
		//get the linked list's length
		ListNode* cur = head;
		int length = 0;
		while(cur){
			length++;
			cur = cur->next;
		}
		
		ListNode dummy(0);
		dummy.next = head;
		ListNode *left, *right, *tail;
		for(int step = 1; step < length; step <<= 1){
			cur = dummy.next;
			tail = &dummy;
			while(cur){
				left = cur;
				right = split(left, step);
				cur = split(right,step);
				tail = merge(left, right, tail);
			}
		}
		return dummy.next;
	}
private:
	/**
	 * Divide the linked list into two lists,
     * while the first list contains first n ndoes
	 * return the second list's head
	 */
	ListNode* split(ListNode *head, int n){
		//if(!head) return NULL;
		for(int i = 1; head && i < n; i++) head = head->next;
		
		if(!head) return NULL;
		ListNode *second = head->next;
		head->next = NULL;
		return second;
	}
	/**
	  * merge the two sorted linked list l1 and l2,
	  * then append the merged sorted linked list to the node head
	  * return the tail of the merged sorted linked list
	 */
	ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
		ListNode *cur = head;
		while(l1 && l2){
			if(l1->val > l2->val){
				cur->next = l2;
				cur = l2;
				l2 = l2->next;
			}
			else{
				cur->next = l1;
				cur = l1;
				l1 = l1->next;
			}
		}
		cur->next = (l1 ? l1 : l2);
		while(cur->next) cur = cur->next;
		return cur;
	}
};