首页 > 代码库 > Leetcode:Partition List

Leetcode:Partition List

2024-07-08 04:51:43   226人阅读

Description:

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.

分析：这道题目就是将链表中小于目标值的元素移到前面，链表中所有元素的相对位置都应该保持不变，其实就是一些

最基本的链表操作，但是这里有一个小trick, 因为每次都要往前看一个元素，以确定操作，所以在链表前面增加一个额外元素，

将所有的操作在循环内就搞定了！

 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 *partition(ListNode *head, int x) {12         if(head == NULL) return head;13         14         ListNode *newh = new ListNode(0);15         newh->next = head;16         17         ListNode *pass= newh, *insertpos=newh, *findnod;18         while(pass->next!=NULL)19         {20             if(pass->next->val>=x)21                 pass = pass->next;22             else if(insertpos->next == pass->next)23                  {24                      pass = pass->next;25                      insertpos = insertpos->next;26                  }27                  else{28                      findnod = pass->next;29                      pass->next = findnod->next;30                      //pass = pass->next;31                      32                      findnod->next = insertpos->next;33                      insertpos->next = findnod;34                      insertpos = insertpos->next;35                  }36         }37         38         return newh->next;39     }40 };

 

 


联系
我们