leetcode_Sort List
설명:
Sort a linked list in O(n log n) time using constant space complexity.
생각:
1. 체인 테이블의 정렬은 일반적으로 만날 때마다 O(nlogn)로 이 문제를 해결하면 어떻게 해야 할지 모르겠다
2. 인터넷의 사고방식을 참고하여 귀속 순서를 정하고 귀속 방법으로 이 문제를 해결하는 것은 괜찮다는 것을 알게 되었다. 이해하기가 좀 힘들다.
3. 중요 절차: 귀속, 통합, 수조의 유효한 범위 내의 중간 노드를 찾고, 질서 있는 수조의 합병
코드:
public ListNode sortList(ListNode head)
{
if(head==null||head.next==null)
return head;
ListNode midNode=getMidNode(head);
ListNode newHead=midNode.next;
midNode.next=null;
head=mergeLists(sortList(newHead), sortList(head));
return head;
}
public ListNode mergeLists(ListNode head1, ListNode head2)
{
if(head1==null&&head2==null)
return head1;
if(head1==null)
return head2;
if(head2==null)
return head1;
ListNode newHead=new ListNode(-1);
ListNode curListNode=newHead;
while(head1!=null&&head2!=null)
{
if(head1.val<head2.val)
{
curListNode.next=head1;
head1=head1.next;
}else
{
curListNode.next=head2;
head2=head2.next;
}
curListNode=curListNode.next;
}
if(head1!=null)curListNode.next=head1;
if(head2!=null)curListNode.next=head2;
return newHead.next;
}
public ListNode getMidNode(ListNode head)
{
if(head==null||head.next==null)
return head;
ListNode p=head,q=head;
while(q.next!=null&&q.next.next!=null)
{
p=p.next;
q=q.next.next;
}
return p;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
