[LeetCode] 86. Partition List 划分链表
2023-09-27 14:28:37 时间
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
给一个链表和一个x值,划分链表,把所有小于x值的节点都移到大于等于x值的前面,两部分的节点顺序不变。
解法:维护两个queue,一个存小于x值的,一个存大于等于x值的,最后在把两个连在一起。记得把大于等于的最后加上null。
Java:
public ListNode partition(ListNode head, int x) { ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0); //dummy heads of the 1st and 2nd queues ListNode curr1 = dummy1, curr2 = dummy2; //current tails of the two queues; while (head!=null){ if (head.val<x) { curr1.next = head; curr1 = head; }else { curr2.next = head; curr2 = head; } head = head.next; } curr2.next = null; //important! avoid cycle in linked list. otherwise u will get TLE. curr1.next = dummy2.next; return dummy1.next; }
Python:
# Time: O(n) # Space: O(1) class ListNode(object): def __init__(self, x): self.val = x self.next = None def __repr__(self): if self: return "{} -> {}".format(self.val, repr(self.next)) class Solution(object): # @param head, a ListNode # @param x, an integer # @return a ListNode def partition(self, head, x): dummySmaller, dummyGreater = ListNode(-1), ListNode(-1) smaller, greater = dummySmaller, dummyGreater while head: if head.val < x: smaller.next = head smaller = smaller.next else: greater.next = head greater = greater.next head = head.next smaller.next = dummyGreater.next greater.next = None return dummySmaller.next
C++:
// Time: O(n) // Space: O(1) /** * 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 dummy_smaller{0}; ListNode dummy_larger{0}; auto smaller = &dummy_smaller; auto larger = &dummy_larger; while (head) { if (head->val < x) { smaller->next = head; smaller = smaller->next; } else { larger->next = head; larger = larger->next; } head = head->next; } smaller->next = dummy_larger.next; larger->next = nullptr; return dummy_smaller.next; } };
C++:
ListNode *partition(ListNode *head, int x) { ListNode node1(0), node2(0); ListNode *p1 = &node1, *p2 = &node2; while (head) { if (head->val < x) p1 = p1->next = head; else p2 = p2->next = head; head = head->next; } p2->next = NULL; p1->next = node2.next; return node1.next; }
All LeetCode Questions List 题目汇总
相关文章
- 【LeetCode】矩阵置零 [M](矩阵)
- 【LeetCode】打砖块 [H](并查集)
- leetCode 61.Rotate List (旋转链表) 解题思路和方法
- Leetcode 326:Power of Three
- leetcode——Remove Duplicates from Sorted List II 删除排序字符串中反复字符(AC)
- [LeetCode] Combinations
- LeetCode_位运算_中等_477.汉明距离总和
- LeetCode_区间问题_中等_452.用最少数量的箭引爆气球
- leetcode day6 -- String to Integer (atoi) && Best Time to Buy and Sell Stock I II III
- LeetCode——Rotate List
- 【LeetCode】LRU Cache
- LeetCode || Copy List with Random Pointer
- Leetcode 丑数
- 「LeetCode合集」链表(List)及经典问题
- LeetCode-28. 实现strStr()(java)
- [LeetCode] 87. Scramble String 爬行字符串
- [LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展平为链表
- [LeetCode] 148. Sort List 链表排序
- [LeetCode] 234. Palindrome Linked List 回文链表
- [LeetCode] 142. Linked List Cycle II 链表中的环 II
- [LeetCode] 141. Linked List Cycle 链表中的环
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项 II
- [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项
- [LeetCode] 206. Reverse Linked List 反向链表
- All LeetCode Questions List 题目汇总
- leetcode 83 删除排序链表中的重复元素