分隔链表

[louzhedong]

习题

出处：LeetCode 算法第86题

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

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

思路

创建两个空的链表，遍历原链表，将小于目标的结点放置于其中一个链表，将大于等于的结点放置于另一个链表，再将两个链表拼接在一起

解答

function ListNode(val) {
  this.val = val;
  this.next = null;
}

var partition = function (head, x) {
  var temp = new ListNode();
  var flag = new ListNode();
  var big = temp;
  var small = flag;
  while (head != null) {
    if (head.val >= x) {
      temp.next = head;
      temp = temp.next;
      head = head.next;
    } else {
      flag.next = head;
      flag = flag.next;
      head = head.next;
    }
  }
  temp.next = null;
  flag.next = null;

  var carry = small;
  while (carry.next != null) {
    carry = carry.next;
  }
  carry.next = big.next;
  return small.next;
};

var head = new ListNode(1);
var aaa = head;
head.next = new ListNode(2);
// head = head.next;
// head.next = new ListNode(3);
// head = head.next;
// head.next = new ListNode(2);
// head = head.next;
// head.next = new ListNode(5);
// head = head.next;
// head.next = new ListNode(2);

console.log(partition(aaa, 2))