Sort_List@LeetCode

1.规定了时间复杂度o(nlogn):采用归并排序，在归并过程：采用分合思想，递归将链表分为两段之后再将merge

分两段方法使用 fast-slow法，用两个指针P1，P2，p1指针每一次走两步，p2指针每一次走一步；当P1指针走到末尾时候，P2指针刚好在中间位置，直到将N序列分成最小子序列单个链表

merge方法：单个链表对合并成有序父链表，比较表头的值，一个P指针指向表头较小值，p指针向后移动，合并至连接到Temp连接表中

1. 采用fast-slow过程中注意 fast=head slow=head

2.在归并merge算法中使用倆个指针 headTemp指针指向其链表首地址，Rear指针遍历之后节点（将其他位置上的节点连接已有地址上来）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *sortList(ListNode *head) {
12         /*拆分最小单子序列 与 单子序列进行合并*/
13         
14         if(head==NULL || head->next==NULL) return head;
15         
16         /*定义fast-slow将链表进行分割*/
17        ListNode *slow=head,*fast=head;
18         //找的中间点从中分为right 与 left
19         while(fast->next && fast->next->next)
20           {
21                 slow=slow->next;
22                 fast=fast->next->next;
23           }
24         
25         ListNode *H1=head,*H2=slow->next;
26         slow->next=NULL;//将分割成俩块
27         
28         H1=sortList(H1);H2=sortList(H2);
29         
30         return merge(H1,H2);
31         
32     }
33     
34     ListNode *merge(ListNode * Left, ListNode * right)
35     
36     {
37         
38         ListNode *headTemp ;/*使用两个指针一个记录开始地址，另外一个地址所有后续节点*/
39         /*必须headTemp指针指向大的值作为开始*/
40         if(Left->val < right->val)
41             {
42                 headTemp=Left;
43                 Left=Left->next;
44             }
45         else
46            {
47                 headTemp=right;
48                 right=right->next;
49            }
50             
51         ListNode *p=headTemp;
52         while(Left!=NULL && right!=NULL)
53           {
54             
55                 if(Left->val<right->val)
56                      {
57                         p->next=Left;
58                         p=p->next;//往后移动指向下一个指针,P失去前一个节点但是
59                                     //headTemp记录前一个节点p=p->next，将其他地址链接到当前地址后面
60                         Left=Left->next;
61                      }
62                     else
63                      {
64                      
65                        p->next=right;
66                         p=p->next;//往后移动指向下一个指针
67                         right=right->next;
68                  }
69           }
70         
71         if(Left==NULL)
72             {
73             p->next=right;
74             }
75         if(right==NULL)
76             {
77             p->next=Left;
78         }
79         
80         return headTemp;
81     }
82    
83 };

此算法用了测试如何建立链表：建立链表中 new 开辟地址，在输入过程中新的链表链接到此上，最后将开始无用链表进行删除

 1 /*从尾部向头部打印*/
 2 #include<iostream>
 3 #include<stack>
 4 using namespace std;
 5 struct ListNode
 6 {
 7     int m_nKey;
 8     ListNode *m_pNext;
 9 };
10 
11 class Solution
12 {
13 public:
14     void PrintListReverse(ListNode * pHead)
15     {
16         /*使用堆栈--后进先出特性*/
17         std::stack<ListNode *> nodes;
18         ListNode *PNode=pHead;
19 
20         while(PNode!=NULL )
21         {
22             nodes.push(PNode);    
23             PNode=PNode->m_pNext;
24         }
25 
26         while(!nodes.empty())
27         {
28             PNode=nodes.top();
29             std::cout<<PNode->m_nKey<<" ";
30             nodes.pop();
31         }
32     }
33 
34 };
35 
36 int main()
37 {
38     ListNode *List=new ListNode();List->m_pNext=NULL;
39 
40     ListNode *pList=List; int m_value;
41     
42     while(true)
43     {
44         cin>>m_value;
45         if(m_value==-1)
46         {
47             
48             pList=NULL;
49             break;
50 
51         }
52         /*开辟新的链表节点，将新的链表节点连接到已有节点上，最后将Head无用节点删除*/
53         ListNode *Rear=new ListNode;
54         Rear->m_nKey=m_value; Rear->m_pNext=NULL;
55         pList->m_pNext=Rear;
56         /*pList指向此新节点*/
57         pList=pList->m_pNext;
58     }
59     /*开始时候多了一个节点*/
60     List=List->m_pNext;
61 
62     Solution S;
63     S.PrintListReverse(List);
64     return 0;
65 }

View Code

快速排序链表方式

单向链表采用快速排序:不同于数组的快速排序，单向链表没有前驱指针，但是其还可以借助快速排序的思想：两个指针prev1=phead，prev2=prev1->next, 两者指针从前遍历到尾，prev2指针先于prev1，当遇到小于基数X值，swap交换prev2->val 和 p->next->val（这样保证p往前移动，直到遇到支点返回)

 1 /*链表快速排序*/
 2 #include<iostream>
 3 using namespace std;
 4 struct ListNode
 5 {
 6     int val;
 7     ListNode *next;
 8     
 9 };
10 
11 ListNode *GetPartion(ListNode *Head,ListNode*end)
12 {
13     ListNode *prev1=Head;
14     ListNode * prev2=prev1->next;
15     int Key=Head->val;
16     /*利用俩个指针从前往后遍历，最后找到一个支点，支点之前小于基数，支点之后大于基数*/
17     while(prev2!=NULL && prev2!=end)
18     {
19         if(prev2->val<Key )
20         {
21             prev1=prev1->next;
22             swap(prev1->val,prev2->val);
23         }
24         prev2=prev2->next;
25     }
26 
27     /*prev1就是支点位置*/
28     swap(prev1->val,Head->val);
29     return prev1;
30 }
31 void QuickSort(ListNode *pHead,ListNode *pEnd)
32 {
33     /*使用两个不同指针从前往后遍历*/
34     if(pHead==NULL || pHead->next==NULL)
35         return;
36     if(pHead!=pEnd)
37     {
38         ListNode * partion=GetPartion(pHead,pEnd);
39         QuickSort(pHead,partion);
40         /*注意在这里必须要partion->next,不然出现明显的死循环问题*/
41         QuickSort(partion->next,pEnd);
42     }
43 
44 }
45 void printQuickSort(ListNode *head)
46 {
47     if(head==NULL)
48     {    cout<<"输入空节点"<<endl;
49     
50 
51         return ;
52     }
53 
54     ListNode *pHead=head;
55     
56     while(pHead!=NULL)
57     {
58         cout<<pHead->val<<" ";
59         pHead=pHead->next;
60     }
61 }
62 int main()
63 {
64     ListNode *List=new ListNode();List->next=NULL;
65 
66     ListNode *pList=List; int m_value;
67     while(true)
68     {
69         cin>>m_value;
70         if(m_value==-1)
71         {
72             
73             pList=NULL;
74             break;
75 
76         }
77         /*开辟新的链表节点，将新的链表节点连接到已有节点上，最后将Head无用节点删除*/
78         ListNode *Rear=new ListNode;
79         Rear->val=m_value; Rear->next=NULL;
80         pList->next=Rear;
81         /*pList指向此新节点*/
82         pList=pList->next;
83     }
84     /*删除开始时候多了一个节点，只有先有地址链表才能够运行*/
85     List=List->next;
86     QuickSort(List,NULL);
87     printQuickSort(List);
88     return 0;
89 }

输入空节点时候，程序并没有崩溃