Leetcode 86. Partition List (Medium) (cpp)
Tag: Linked List, Two Pointers
Difficulty: Medium
/* 86. Partition List (Medium) 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. */ /** * 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) { if (head == NULL || head -> next == NULL) { return head; } ListNode *s = new ListNode(-1), *g = new ListNode(-1); ListNode *p = s, *q = g; while (head != NULL) { if (head -> val < x) { p -> next = head; p = p-> next; } else { q -> next = head; q = q -> next; } head = head -> next; } p -> next = g -> next; q -> next = NULL; return s -> next; } };
