首页 > 代码库 > 算法--链表的分化
算法--链表的分化
转载请标明出处http://www.cnblogs.com/haozhengfei/p/c4d685012a2e7a9d2a29531f249be630.html
链表的分化
链表的分化练习
第5节 链表的分化练习题
对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。
给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。
测试样例：
{1,4,2,5},3
{1,2,4,5}
1
import java.util.*;
2
3
/*
4
public class ListNode {
5
int val;
6
ListNode next = null;
7
8
ListNode(int val) {
9
this.val = val;
10
}
11
}*/
12
public class Divide {
13
public ListNode listDivide(ListNode head, int val) {
14
ListNode smallHead = null, smallTail = null;
15
ListNode bigHead = null, bigTail = null;
16
17
ListNode next = null;
18
while (head != null) {
19
next = head.next;
20
head.next = null;
21
if (head.val <= val) {
22
if (smallHead == null) {
23
smallHead = head;
24
smallTail = head;
25
} else {
26
smallTail.next = head;
27
smallTail = head;
28
}
29
} else {
30
if (bigHead == null) {
31
bigHead = head;
32
bigTail = head;
33
} else {
34
bigTail.next = head;
35
bigTail = head;
36
}
37
}
38
head = next;
39
}
40
// 拼接
41
if (smallTail != null)
42
smallTail.next = bigHead;
43
return smallHead == null ? bigHead : smallHead;
44
}
45
}
您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例
答案正确:恭喜！您提交的程序通过了所有的测试用例
算法--链表的分化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。