【leetcode每日一题】NO86.Partition List

拼搏现实的明天。 2022-08-04 04:05 140阅读 0赞

题目：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.

解析：先声明两个指针result1和result2，遍历链表，当节点小于x的时候，result1指向该节点，当节点大于或等于x的时候，result2指向该节点。最后再把生成的两个链表进行合并即可。

代码：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *partition(ListNode *head, int x) {
            ListNode *result1=new ListNode(0);
            ListNode *result2=new ListNode(0);
            ListNode *temp1=result1;
            ListNode *temp2=result2;
            while(head!=NULL)
            {
                if(head->val<x)
                {
                    temp1->next=head;
                    temp1=temp1->next;
                }
                else
                {
                    temp2->next=head;
                    temp2=temp2->next;
                }
                head=head->next;
            }
            temp1->next=result2->next;
            temp2->next=NULL;
            return result1->next;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode86——Partition List

LeetCode86——Partition List 将链表按某个值划分，小的节点在前，大的节点在后，整体仍然保持原来的大小顺序。 ------------------

左手的ㄟ右手/ 2022年08月20日 04:11/ 0 赞/ 125 阅读

相关【leetcode每日一题】NO92.Reverse Linked List II

题目：Reverse a linked list from position m to n. Do it in-place and in one-pass. For

清疚/ 2022年08月04日 04:14/ 0 赞/ 142 阅读

相关【leetcode每日一题】NO86.Partition List

题目：Given a linked list and a value x, partition it such that all nodes less than x come

拼搏现实的明天。/ 2022年08月04日 04:05/ 0 赞/ 141 阅读

相关【leetcode每日一题】NO206.Reverse Linked List

题目：Reverse a singly linked list.即单链表反序。解析：链表反序是很常见的题目，不过多解释了，直接上代码。 / Defin

朴灿烈づ我的快乐病毒、/ 2022年08月03日 23:55/ 0 赞/ 177 阅读

相关 leetcode 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come bef

阳光穿透心脏的1/2处/ 2022年06月08日 02:27/ 0 赞/ 141 阅读

相关 LeetCode 86.Partition List (分隔链表)

题目描述：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:

àì夳堔傛蜴生んèń/ 2022年05月10日 10:14/ 0 赞/ 170 阅读

相关 86. Partition List

/ Definition for singly-linked list. struct ListNode { int val

╰半夏微凉°/ 2022年04月03日 13:28/ 0 赞/ 138 阅读

相关【Leetcode】86. Partition List

Given a linked list and a value x, partition it such that all nodes less than xcome befo

Love The Way You Lie/ 2022年02月23日 12:18/ 0 赞/ 144 阅读

相关 LeetCode 86. Partition List 20170612

Given a linked list and a value x, partition it such that all nodes less than x come bef

快来打我*/ 2021年12月23日 11:49/ 0 赞/ 161 阅读

相关 [LeetCode] 86. Partition List_Medium tag: Linked List

Given a linked list and a value x, partition it such that all nodes less than x come bef

悠悠/ 2021年12月11日 22:57/ 0 赞/ 168 阅读