题目

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:

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

题意

给定一个链表和目标值x，将链表中所有值小于x的结点移到所有值大于等于x的结点的前面，同时不能改变值小于/大于等于x的结点的相对位置。

思路

新建两个头结点分别用来保存原链表中值小于x的结点和值大于等于x的结点，最后将两链表相连即为所求的新链表。

代码实现

Java

  1. class Solution {
  2.     public ListNode partition(ListNode head, int x) {
  3.         // 建空的头结点便于处理
  4.         ListNode leftHead = new ListNode(0), leftTail = leftHead;
  5.         ListNode rightHead = new ListNode(0), rightTail = rightHead;
  7.         while (head != null) {
  8.             if (head.val < x) {
  9.                 leftTail.next = head;
  10.                 leftTail = head;
  11.             } else {
  12.                 rightTail.next = head;
  13.                 rightTail = head;
  14.             }
  15.             head = head.next;
  16.         }
  18.         rightTail.next = null;                // 注意断链，否则可能会形成环
  19.         leftTail.next = rightHead.next;        // 拼接链表
  21.         return leftHead.next;
  22.     }
  23. }

JavaScript

  1. /**
  2.  * @param {ListNode} head
  3.  * @param {number} x
  4.  * @return {ListNode}
  5.  */
  6. var partition = function (head, x) {
  7.   const dummyA = new ListNode()
  8.   const dummyB = new ListNode()
  9.   let A = dummyA
  10.   let B = dummyB
  12.   while (head) {
  13.     const next = head.next
  14.     head.next = null
  15.     if (head.val < x) {
  16.       A.next = head
  17.       A = A.next
  18.     } else {
  19.       B.next = head
  20.       B = B.next
  21.     }
  22.     head = next
  23.   }
  25.   A.next = dummyB.next
  26.   return dummyA.next
  27. }