链表的分割——哨兵位

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路，把链表分成两个新链表，然后连接起来

代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead==NULL)
        {
            return pHead;
        }
         ListNode* ghead=NULL;
         ListNode* gtail=NULL;
         ListNode* lhead=NULL;
         ListNode* ltail=NULL;
         ListNode* cur=pHead;
         while(cur)
         {
            if(cur->val<x)
            {
                if(ltail==NULL)
                {
                    lhead=ltail=cur;
                }else 
                {
                    ltail->next=cur;
                    ltail=ltail->next;
                }
                cur=cur->next;
            }else
            {
               if(gtail==NULL)
               {
                ghead=gtail=cur;
               } else{
                gtail->next=cur;
                gtail=gtail->next;
               }
               cur=cur->next;
            }
         }
         if(gtail)//储存大的那个那个链表如果不是空，那么就要把最后一个节点的next置空
         {
         gtail->next=NULL;

         }
          else//如果gtail是空的话,那么就全都是小的数在lhead里，直接返回那么链表就行
         {
            return pHead;
         }
         if(lhead)
         {
            ltail->next=ghead;
             return lhead;
         }else {
         return lhead;
         }
        
         
        
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

判断头的代码过于繁琐，那么就利用链表的标兵：

代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead==NULL)
        {
            return pHead;
        }
         ListNode* ghead=NULL;
         ListNode* gtail=NULL;
         ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
         ListNode* lhead=NULL;
         ListNode* ltail=NULL;
         lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));

         ListNode* cur=pHead;
         while(cur)
         {
            if(cur->val<x)
            {
               
                    ltail->next=cur;
                    ltail=ltail->next;
                
                
            }else
            {
               
                gtail->next=cur;
                gtail=gtail->next;
               
            }
               cur=cur->next;

         }
         
         gtail->next=NULL;

         
          ltail->next=ghead->next;
          struct ListNode* per=lhead->next;
          free(lhead);
          free(ghead);

         return per;
         
        
         
        
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52