Partition List（链表的插入和删除操作，找前驱节点）

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

思路：

1.由于不能改变原来的相对位置，所以直接置换值是不行的。

2.其实这个题类似于快速排序的Partition函数，该思路是，随机从数组中选取一个值作为参考值，使得数组中比该参考值小的数字排在参考值左端,数组中比该参考值大的数字排在参考值右端。

遍历所有节点，发现比x小的节点就”交换“，交换的过程即先删除那个节点，然后插入到对应位置。

这里有一个前提，即若第一个数就小于x的话，是不需要“交换的”。

另外一点需要注意的是：删除链表某个节点之后，指针p的值可能出现不定义状态，故在删除之前，先让p指向要删除节点的下一个节点。

 class Solution {

 public:

     //删除链表中位置为loc的节点，从1开始

     int Delete(ListNode* &head,int loc){

         ListNode* p=NULL;

         ListNode* q=NULL;

         p=head;

         int i=;

         //找到前驱节点

         while(i<loc-&&p->next){

             ++i;

             p=p->next;

         }

         q=p->next;

         p->next=q->next;

         int val=q->val;

         free(q);

         return val;

     }

     ListNode* Insert(ListNode* &head,int loc,int val){

         ListNode* p=head;

         p=head;

         int i=;

         if(loc==){

             ListNode* s=(ListNode*)malloc(sizeof(ListNode));

             s->val=val;

             s->next=p;

             return s;

         }

         //找到前驱节点

         while(i<loc-&&p->next){

             ++i;

             p=p->next;

         }

         ListNode* s=(ListNode*)malloc(sizeof(ListNode));

         s->val=val;

         s->next=p->next;

         p->next=s;

         return head;

     }

     ListNode *partition(ListNode *head, int x) {

         if(head==NULL) return NULL;

         int insertloc=;

         int loc=;

         ListNode* p=head;

         while(p!=NULL)

         {

             ++loc;

             if(p->val<x)

             {

                 ++insertloc;

                 if(insertloc!=loc){

                     p=p->next;

                     int val=Delete(head,loc);

                     head=Insert(head,insertloc,val);

                     continue;

                 }

             }

             p=p->next;

         }

         return head;

     }

 };

巴特西

Partition List（链表的插入和删除操作，找前驱节点）

最新文章

热门文章