單鏈表快速歸并插入排序

目錄

插入排序

快速排序

歸并排序

冒泡排序

插入排序

對應letecode鏈接：

力扣

題目描述：

給你鏈表的頭結點 head ，請將其按 升序 排列并回傳 排序后的鏈表 ，

進階：

你可以在 O(n log n) 時間復雜度和常數級空間復雜度下，對鏈表進行排序嗎？

示例 1：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
示例 2：
輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
示例 3：

輸入：head = []
輸出：[]

提示：

鏈表中節點的數目在范圍 [0, 5 * 104] 內
-105 <= Node.val <= 105

主要介紹一下快速排序，歸并排序，插入排序，冒泡排序：

插入排序：

解題思路：

鏈表與陣列的插入排序不同，陣列支持隨機訪問，而鏈表是不支持隨機訪問的，我們在陣列中可以隨意的前后移動，將指標指向值和新元素的值比較后，將新元素插入到合適的位置，我們知道鏈表查詢元素的時間復雜度為 O（n）,我們只能夠通過遍歷鏈表查詢元素，那么我們怎么才能將新元素放到合適的位置呢？

我們可以將第一個節點從鏈表中取下來構造一個新的鏈表：

將剩余的節點插入到1這個節點之中插入分為3種情況：

1.頭插

2.中間插入

3.尾插

程序：

情況1：

1.如果取鏈表的節點插入到新的鏈表中如果要插入的節點比新鏈表的頭節點還要小此時我們只需要將這個節點頭插到新鏈表中即可

此時cur指向的節點對應val的值小于newhead所對應的val值此時將其頭插即可也就是：cur->next=newhead;newhead=cur;

但是我們將cur的next指向newhead了就找不到后面的節點，所以我們需要定義一個變數next保存下一個節點

情況二：

當cur的val比newhead的val要小并且是在中間插入時我們需要定義一個變數newheadcur和newheadprev變數新鏈表通過比較值找到對應的插入位置

將其插入進去即可

情況三：

cur所在節點對應的值比新鏈表的值都要大這是就要進行尾插

對應代碼：

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
                 if(!head||!head->next){//空節點或者只有一個節點直接回傳即可
                     return head;
                 }
            ListNode*cur=head->next;//遍歷剩下的節點
            ListNode*newhead=head;
             head->next=nullptr;//將第一節點從鏈表中取下
            while(cur){
            ListNode*next=cur->next;//保存下一節點
            //頭插
             if(cur->val<newhead->val){
                 cur->next=newhead;
                 newhead=cur;
             }else{
                ListNode*newheadcur=newhead->next;
                ListNode*newheadprev=newhead;
                //遍歷新鏈表
                while(newheadcur){
                    //找到插入位置
                     if(newheadcur->val>cur->val){
                            newheadprev->next=cur;//鏈接
                            cur->next=newheadcur;
                            break;//插入完成結束回圈
                     }else{
                          newheadprev=newheadcur;
                          newheadcur=newheadcur->next;
                     }
                }
                //尾插
                if(newheadcur==nullptr){
                    newheadprev->next=cur;
                    cur->next=nullptr;//防止成環
                }
             }
               cur=next;
            }
            return newhead;

    }
};

快速排序

解題思路：

很多老鐵可能想說鏈表怎么快速排序鏈表只能正著走不能夠倒著走怎么使用快速排序其實快速排序的前后指標法是不涉及下標的：

如果不清楚的老鐵可以去看一下我的排序博客

具體步驟：

我們可以選取頭節點作為基準值，遍歷鏈表，將比它小的節點頭插在它前面，比它大的節點尾插在它后面
假設smallHead維護的是小于基準值的頭插指標，greaterHead維護的是大于等于基準值的尾插指標
則一次對[head , end）快排結束后有
-[ smallHead , head ) （左閉右開）是小于基準值的一部分
-[ head->next , end ) （左閉右開）是大于等于基準值的一部分
再分治這兩部分即可

對應代碼：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
         return quick_sortListNode(head,nullptr);
    }
    ListNode*quick_sortListNode(ListNode*head,ListNode*end){
                 if(head==end||head->next==end){
                      return head;//一個節點或者沒有節點回傳head即可
                 }
                 ListNode*smallHead=head;
                 ListNode*greaterHead=head;
                 ListNode*cur=head->next;
                 int key=head->val;
                 //選取第一個值做key
                 while(cur!=end){
                 ListNode*next=cur->next;//保存cur的下一個節點
                 //頭插
                 if(cur->val<key){
                     cur->next=smallHead;
                     smallHead=cur;
                 }else{
                      greaterHead->next=cur;
                      greaterHead=greaterHead->next;
                 }
                 cur=next;
        }
            greaterHead->next=end;//鏈接最后一個節點
          //遞回兩部分
          ListNode*ans=quick_sortListNode(smallHead,head);
          head->next=quick_sortListNode(head->next,end);
          return ans;
    }
};

歸并排序

解題思路：

歸并排序，逃脫不了，分合， 思路如下：

分割 -> 通過遞回不斷分割鏈表，在此程序中需要保證鏈表不丟失的情況下，不斷想下切割 （e.g. 8 -> 4 -> 2）
關鍵在于找到鏈表的中心點， 并從中心點將鏈表分割成 2 部分，
我們可以使用經典的快慢雙指標鏈表分割方法，其中有個點需要注意，鏈表長度為奇偶，切割處理方式是不同的，這里根據大家喜歡的方式處理即可，這里沒有明確規定必須使用什么切割方式，筆者的切換策略如下：
快指標每次移動 2 步，慢指標每次移動 1?? 步，當快指標到達鏈表末尾時，慢指標指向的鏈表節點即為鏈表的中點，
找到中點后，將鏈表進行斷開，將當前鏈表分成 2 部分
對兩個鏈表分別排序，慢指標的下一節點，指向空即可
分割階段結束 -> 遞回退出 -> 直到分割的鏈表長度為 1，此時遞回到底了
merge 環節，退出遞回的程序中，不斷的排序合并merge 節點，其實包含在分割階段里邊，merge -> 排序當前鏈表，

對應分割鏈表代碼：

 ListNode*splitListNode(ListNode*head){
        if(!head||!head->next)return head;
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;
        while(fast&&fast->next){
            prev=slow;
            fast=fast->next->next;
            slow=slow->next;
        }

        return prev;
    }

注意中間那個節點要分給對分割的第二段鏈表

如果只有兩個節點的話，slow指向的就是第二個節點，如果將其分給第一個合并的鏈表那么就會死回圈！！！！

合并鏈表對應代碼：

ListNode*mergeListNode(ListNode*head1,ListNode*head2){
            ListNode*dummyHead=new ListNode(-1);
            ListNode*ans=dummyHead;
              while(head1&&head2){
                  if(head1->val<=head2->val){
                      ans->next=head1;
                      ans=ans->next;
                      head1=head1->next;
                  }
                  else{
                      ans->next=head2;
                      ans=ans->next;
                      head2=head2->next;
                  }
              }
              if(head1)ans->next=head1;
              if(head2)ans->next=head2;
              return dummyHead->next;
       }

上面的操作都在之前的鏈表博客里面解釋過了如果不太清楚的老鐵可以去看一下我之前的博客

總代碼：

class Solution {
public:
    ListNode*splitListNode(ListNode*head){
        if(!head||!head->next)return head;
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;
        while(fast&&fast->next){
            prev=slow;
            fast=fast->next->next;
            slow=slow->next;
        }

        return prev;
    }

     ListNode*mergeListNode(ListNode*head1,ListNode*head2){
            ListNode*dummyHead=new ListNode(-1);
            ListNode*ans=dummyHead;
              while(head1&&head2){
                  if(head1->val<=head2->val){
                      ans->next=head1;
                      ans=ans->next;
                      head1=head1->next;
                  }
                  else{
                      ans->next=head2;
                      ans=ans->next;
                      head2=head2->next;
                  }
              }
              if(head1)ans->next=head1;
              if(head2)ans->next=head2;
              return dummyHead->next;
       }

    ListNode* sortList(ListNode* head) {
               if(!head||!head->next)return head;
               ListNode*mid=splitListNode(head);
               ListNode*midNext=mid->next;
               mid->next=nullptr;
               //化分鏈表
               ListNode*head1=sortList(head);
             ListNode*head2= sortList(midNext);
          return mergeListNode(head1,head2);
    }
   
};

冒泡排序

冒泡排序就比較簡單了在這里就直接給出代碼：

對應代碼：

void  BubbleSort(struct Node* headNode)
{
	struct Node* firstNode = headNode->next;
	struct Node* secondNode = headNode;
	while (firstNode != NULL)
	{
		while (firstNode->next != NULL)
		{
			if (firstNode->data > firstNode->next->data)
			{
				int temp = firstNode->data;
				firstNode->data = firstNode->next->data;
				firstNode->next->data = temp;
			}
			firstNode = firstNode->next;
		}
		//減少排序次數
		firstNode = secondNode->next;
		secondNode = firstNode;
	}

}

如果覺得不錯的老鐵可以點個贊