1. 问题描述:
编写代码,以给定值x为基准将链表分为两部分,所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头结点 ListNode * pHead,请返回重新后的链表的头指针
注意:分割以后原来的数据顺序不变
不要开辟新的空间,即不要新建节点
2. 我们可以定义几个指针把给出的链表分为两部分,左边的链表元素值小于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
64
65
66
67
68public class Main { private static class ListNode{ private ListNode next; private int value; public ListNode(int value) { super(); this.value = value; } } public static void main(String[] args) { int arr[] = {5, 6, 3, 1, 2, 8}; ListNode head = new ListNode(arr[0]); ListNode p = head; for(int i = 1; i < arr.length; i++){ p.next = new ListNode(arr[i]); p = p.next; } p = head; while(p != null){ System.out.print(p.value + " "); p = p.next; } System.out.print("n"); int n = 3; ListNode node = partition(head, n); while(node != null){ System.out.print(node.value + " "); node = node.next; } } private static ListNode partition(ListNode head, int n) { ListNode p = head; ListNode leftFirst = null; ListNode leftTail = null; ListNode rightFirst = null; ListNode rightTail = null; while(p != null){ if(p.value < n){ if(leftFirst == null){ leftFirst = p; leftTail = p; }else{ leftTail.next = p; leftTail = leftTail.next; } }else{ if(rightFirst == null){ rightFirst = p; rightTail = p; }else{ rightTail.next = p; rightTail = rightTail.next; } } p = p.next; } //判断左边的链表是否为空 if(leftFirst == null){ return rightFirst; } leftTail.next = rightFirst; //一定要写上下面的if判断语句假如不写会出现错误 if (rightTail != null) rightTail.next = null; return leftFirst; } }
最后
以上就是安详小土豆最近收集整理的关于使用基准值对链表进行分区的全部内容,更多相关使用基准值对链表进行分区内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复