链表21 -- 分割链表

心已赠人 2022-05-25 08:48 279阅读 0赞

1、题目:

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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
    Output: 1->2->2->4->3->5

2、解答：思想就是，用一个指针指向比x小的值，另外一个值指向比它大的值。然后合并两个链表

3、C++代码：

class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            if(!head)
                return head;
            ListNode *curr = head;
            ListNode *dummy = new ListNode(0);
            ListNode *dummy1 = new ListNode(0);
            ListNode *p = dummy;
            ListNode *q = dummy1;
            while(curr){
                if(curr->val < x){
                    p->next = curr;
                    p = p->next;
                }else{
                    q->next = curr;
                    q = q->next;
                }
                curr = curr->next;
            }
            q->next = NULL;
            p->next = dummy1->next;
            return dummy->next;
        }
    };

python代码：

class Solution:
        def partition(self, head, x):
            """
            :type head: ListNode
            :type x: int
            :rtype: ListNode
            """
            head1 = l1 = ListNode(0)
            head2 = l2 = ListNode(0)
            
            while head:
                if head.val < x:
                    l1.next = head
                    l1 = l1.next
                else:
                    l2.next = head
                    l2 = l2.next
                head = head.next
                
            l2.next = None
            l1.next = head2.next
            return head1.next