题解 | 划分链表
划分链表
http://www.nowcoder.com/practice/1dc1036be38f45f19000e48abe00b12f
题意分析：
- 一个原始链表，一个整数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;
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
小白专属-牛客题解 文章被收录于专栏
专注于牛客平台编程题题解，文字+图解。内容很细，小白友好系列
，博主觉得技术积累和资源积累哪个更重要呢