首页 > 代码库 > Leetcode SortList
Leetcode SortList
Sort a linked list in O(n log n) time using constant space complexity.
本题利用归并排序即可
归并排序的核心是将两部分合成一部分，
故开始要将链表分成两部分，利用快慢两个指针，当快指针跑到链表尾部时，慢指针恰好在中间，故可以将链表分成两部分
然后将两个链表合并，注意可以新建一个新节点，作为链表头结点，利用new新建节点后，要注意用delete删除节点，保持良好的编程习惯
#include <iostream>#include <vector>using namespace std;struct ListNode{ int val; ListNode *next; ListNode(int x):val(x), next(NULL){}};void printList(ListNode* head){ while(head!=NULL){ cout<<"->"<<head->val; head = head->next; } cout<<endl;}ListNode *merge(ListNode *head1, ListNode *head2){ // cout<<"======"<<endl; // printList(head1); // printList(head2); // cout<<"----->"<<endl; if(head1 == NULL ) return head2; if(head2 == NULL) return head1; ListNode *mergeHead = new ListNode(-1); ListNode *pre = mergeHead; mergeHead->next = head1; while(head1!=NULL && head2 != NULL){ if(head1->val < head2->val) head1= head1->next; else{ ListNode *node = head2->next; head2->next = pre->next; pre->next = head2; head2 = node; } pre = pre->next; } if(head2!=NULL) pre->next = head; ListNode *res = mergeHead->next; delete mergeHead; return res; } ListNode *mergeSort(ListNode *head){ if(head == NULL || head->next == NULL) return head; ListNode *slow = head; ListNode *fast = head; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; } ListNode* head2 = slow->next; slow->next = NULL; ListNode* head1 = head; head1 = mergeSort(head1); head2 = mergeSort(head2); return merge(head1,head2);}ListNode *sortList(ListNode *head){ return mergeSort(head);}int main(){ ListNode* head = new ListNode(3); ListNode* node1 = new ListNode(2); ListNode* node2 = new ListNode(4); head->next = node1; node1->next = node2; ListNode *a = sortList(head); cout<<"ans:"<<endl; printList(a);}
本题更复杂一点的是
给出两个无序链表，然后将其合并，
首先要做的事将无序链表排序，然后将两个有序链表合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。