연결된 정수 목록을 정렬 하시겠습니까?

Question

나는 LinkedList을 소트해야하는데 (int을 포함하고 있습니다.) 어떻게해야하는지 모르겠습니다. 누구든지 int 링크 된 목록을 정렬하려면 내 소스 코드를 줄 수 있습니까?

나는이 코드를 온라인에서 찾았지만 작동하지 않았습니다.

public void sort(LinkedList sortlist) 
{ 
    //Enter loop only if there are elements in list 
    boolean swapped = (head != null); 

    // Only continue loop if a swap is made 
    while (swapped) 
    { 
     swapped = false; 

     // Maintain pointers 
     Node curr = head; 
     Node next = curr.link; 
     Node prev = null; 

     // Cannot swap last element with its next 
     while (next != null) 
     { 
      // swap if items in wrong order 
      if (curr.data>next.data) 
      { 
       // notify loop to do one more pass 
       swapped = true; 

       // swap elements (swapping head in special case 
       if (curr == head) 
       { 
        head = next; 
        Node temp = next.link; 
        next.link = curr; 
        curr.link = temp; 
        curr = head; 
       } 
       else 
       { 
        prev.link = curr.link; 
        curr.link = next.link; 
        next.link = curr; 
        curr = next; 
       } 
      } 

      // move to next element 
      prev = curr; 
      curr = curr.link; 
      next = curr.link; 
     } 
    } 
} 

Answer 1

스탠포드의 CS106B 코스에 대한 C++ implementation of merge sort on linked lists given in this handout 있습니다. 그것은 시간 O (n log n)에서 실행됩니다. 이것은 매우 좋습니다.

다른 접근법에 대한 설문 조사는 연결된 목록을 정렬하는 방법에 대해서는 this older SO answer을 확인하십시오. 여기에는 코드가 없지만 기존 아이디어를 링크 된 목록에 적용하는 방법을 잘 설명하고 있습니다.

희망이 도움이됩니다.

Answer 2

병합 정렬과 빠른 정렬을 사용하여 링크 목록 (평균 O (n.long))을 정렬 할 수 있습니다. 또한 숫자가 정수인 경우 기수 정렬을 변형하여 O (n)을 처리하고 그 자리에 있습니다. 따라서 링크 목록을 배열로 변환 할 필요가 없습니다.