LeetCode 148 排序链表

题目：

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

解题思路：

可达到O(nlogn)的排序我们知道有三种，堆排、快排、二路归并。这里由于是链表，堆排和归并都不太容易操作。所以这里我们用二路归并算法。

二路归并有递归的和非递归的，这里单链表，用非递归较为简单。因为递归要比较两个区间的大小，这里需要用到双指针。

代码：

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode* sortList(ListNode* head) {

         if(head == NULL)

             return NULL;

         ListNode *p = head;

         int len = ;

         while(p) {

             len++;

             p = p->next;

         }

         ListNode *temp = new ListNode();

         temp->next = head;

         int interval;

         for(interval = ; interval <= len; interval *= ) { //从下往上归并

             ListNode *pre = temp;

             ListNode *first = temp->next;

             ListNode *second = temp->next;

             while(first && second) {

                 int i = ;

                 while(i < interval && second) {

                     second = second->next;

                     i++;

                 }

                 int fvisit = ;

                 int svisit = ;

                 while(fvisit < interval && svisit < interval && first && second) {

                     if(first->val < second->val) { //前指针较小，则把前指针装入放在前头

                         pre->next = first;

                         pre = first;

                         first = first->next;

                         fvisit++;

                     }

                     else {

                         pre->next = second;

                         pre = second;

                         second = second->next;

                         svisit++;

                     }

                 }

                 while(fvisit < interval && first) {//剩下的较大的就依次接上就好

                     pre->next = first;

                     pre = first;

                     first = first->next;

                     fvisit++;

                 }

                 while(svisit < interval && second) {

                     pre->next = second;

                     pre = second;

                     second = second->next;

                     svisit++;

                 }

                 pre->next = second; //往后继续直到第一次排序结束

                 first = second;

             }

         }

         ListNode *ans = temp->next;

         delete temp;

         return ans;

     }

 };

巴特西

LeetCode 148 排序链表

最新文章

热门文章