题目

86. Partition List

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

解答

分离链表，可以初始化另个链表，一个都小于某个值，一个大于等于某个值，最后拼接起来即可。这里需要注意：最后一个节点的next需要设置为null，否则会导致死循环。或者每个节点都根据val重新创建一个避免这种问题。

重新定义链表，用于打印输出

package common;

public class ListNode {
    public int val;
    public  ListNode next;
    public ListNode(int val) {
        this.val = val;
    }

    static public ListNode listNodeWithIntArray(int[] input) {
        ListNode head = new ListNode(0);
        ListNode node = head;

        for (int i: input) {
            ListNode newNode = new ListNode(i);
            node.next = newNode;
            node = node.next;
        }

        return head.next;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode node = this;
        while (node != null) {
            sb.append(node.val).append("-->");
            node = node.next;
        }
        return sb.append("Null").toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        return false;
    }
}

算法实现

package linkedlist;

import common.ListNode;

// https://leetcode.com/problems/partition-list/
public class PartitionList {

  public ListNode partition(ListNode head, int x) {
    // check edge
    if (head == null || head.next == null) {
      return head;
    }

    ListNode smallNode = new ListNode(0);
    ListNode smallHead = smallNode;
    ListNode bigNode = new ListNode(0);
    ListNode bigHead = bigNode;

    while (head != null) {
      if (head.val < x) {
        smallNode.next = head;
        smallNode = smallNode.next;
      } else {
        bigNode.next = head;
        bigNode = bigNode.next;
      }

      head = head.next;
    }

    // warning: need to set last next to null, otherwise it will infinite loop.
    bigNode.next = null;
    smallNode.next = bigHead.next;

    return smallHead.next;
  }
}