题解 | 划分链表

题意分析：

• 一个原始链表，一个整数x,对该链表进行如下规则的操作。
  • 以x为分界，将链表划分为两部分。val<x和val>=x
  • 两个部分之内的节点之间要保持的原始相对顺序

解法一：模拟（推荐）

思路步骤：

由于要将链表按照规则分割为两部分，可以考虑维护两个链表small和large。同样使用哑节点技巧(smallHead和largeHead)

• 开始时：smallHead.next = small,largeHead.next = large

• 遍历原始链表，发现head.val<x。

• 执行：small.next = head.

• 否则：large.next = head.

• 最后要将large 的next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点

• 将small的next节点置空。

• 完整图解：
  

  Java参考代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // 创建哑节点和两个链表
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        //对链表进行规则划分
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = small.next;
            }else{
                large.next = head;
                large =large.next;