题目描述
思路
- 可以将链表分成两个小链表，一个链表中的元素大小都小于x，另一个链表中的元素都大于等于x，然后再把这两条链表连接到一起，就得到题目想要的结果。
- 这个题类似于合并两个有序链表：只不过另一个链表只有唯一一个节点x。
合并这两个链表。
方法一：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
// dummy1链表用于存所有小于x的节点
ListNode dummy1 = new ListNode();
// dummy2链表用于存储所有大于等于x的节点
ListNode dummy2 = new ListNode();
// p用来遍历dummy1链表,q用来遍历dummy2链表,cur用来遍历head链表
ListNode p = dummy1, q = dummy2, cur = head;
while (cur != null) {
if (cur.val < x) {
p.next = cur;
p = cur;
} else {
q.next = cur;
q = cur;
}
cur = cur.next;
}
// 如果cur为null了，则将p和q的next都指向null
// 如果不这样操作的话，会导致链表有环
p.next = null;
q.next = null;
p.next = dummy2.next;
return dummy1.next;
}
}