链表分割（解题报告）

134 阅读 0 评论 89 点赞

我是靠谱客的博主坦率画板，这篇文章主要介绍链表分割（解题报告），现在分享给大家，希望可以做个参考。

题目描述

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

解题思路：用两个链表保存，一个大于等于x的链表，另一个是小于x的链表。最后合并两个链表即可。

注意分支的保存。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package link;
public class Partition {
public static void main(String [] args){
ListNode pHead=new ListNode(6);
pHead.next=new ListNode(2);
pHead.next.next=new ListNode(8);
pHead=partition(pHead,2);
while(pHead!=null){
System.out.println(pHead.val);
pHead=pHead.next;
}
}
public static ListNode partition(ListNode pHead, int x) {
ListNode large=null;
ListNode largetail=null;
ListNode small=null;
ListNode smalltail=null;
ListNode current=pHead;
while(current!=null){
if(current.val>=x){
if(large==null){
large=current;
largetail=current;
}
else{
largetail.next=current;
largetail=current;
}
}
else {
if(small==null){
small=current;
smalltail=current;
}
else{
smalltail.next=current;
smalltail=current;
}
}
current=current.next;
}
if(small==null){
current=large;
largetail.next=null;
}
else{
current=small;
smalltail.next=large;
if(large!=null){
largetail.next=null;
}
}
return current;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}