[LeetCode]面试题 02.04 分割链表 and 86.分割链表

15
2020/07

# [LeetCode]面试题 02.04 分割链表 and 86.分割链表

## 题目

https://leetcode-cn.com/problems/partition-list-lcci/

Related Topics 链表 双指针
👍 21 👎 0

## 分析及反思

p指针左边必定是小于x的节点，q指针遍历链表，遇到val<x时，交换p,q的val，并且p=p.next

https://leetcode-cn.com/problems/partition-list/

## 代码

info

class Solution {

public ListNode partition(ListNode head, int x) {
ListNode p, q;
while (q != null) {
if (q.val < x) {//肯定是大于等于的交换
int t = q.val;
q.val = p.val;
p.val = t;
p = p.next;
}
q = q.next;
}
}
}

## 86题 保持后者的大小相对顺序

11:06 info

class Solution {
public ListNode partition(ListNode head, int x) {
//维护两条链表，利用尾插法保证相对顺序不变
ListNode min = new ListNode(-1);
ListNode max = new ListNode(-1);
ListNode p = head, p1 = min, p2 = max;//mark 链表的头。

while (p != null) {
if (p.val < x) {
min.next = p;
min = min.next;
} else {
max.next = p;
max = max.next;
}
p = p.next;
}
min.next = p2.next;//小的尾巴指向大的头部 尾插法
max.next = null;///对于非空表，将尾结点指针域置空 否则 Error - Found cycle in the ListNode
return p1.next;
}
}

百度已收录

Last modification：July 15th, 2020 at 11:26 am