leetcode 86. 分隔链表

问题描述

给定一个链表和一个特定值 x，对链表进行分隔操作，使得所有小于 x 的节点排在前面，所有大于或等于 x 的节点排在后面。你应当保留两个分区中元素的相对顺序。

示例:

输入: head = 1->4->3->2->5, x = 3
输出: 1->2->4->3->5

解法一

解题思路:

我们需要遍历链表，将小于 x 的节点和大于等于 x 的节点分别连接起来，最后将两个链表合并。

/** @lc app=leetcode.cn id=86 lang=javascript** [86] 分隔链表*/// @lc code=start
function partition(head, x) {let dummy1 = new ListNode(0);let dummy2 = new ListNode(0);let cur1 = dummy1;let cur2 = dummy2;let cur = head;while (cur) {if (cur.val < x) {cur1.next = cur;cur1 = cur1.next;} else {cur2.next = cur;cur2 = cur2.next;}cur = cur.next;}cur1.next = dummy2.next;cur2.next = null;return dummy1.next;
}
// @lc code=end