链表例题3：用基准值将链表分区

佚名 5年前 (2018-12-31) 算法 797人围观抢沙发百度已收录

解题思路：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1.创建一个结点类。

2.创建一个分割方法。

3.声明四个结点分别存储小于基准值,大于或等于基准值(注意这里是声明结点,不是实例化结点,所以不算违规)。

四个声明的结点为(定义四个结点是为了最后好进行链接在一起)：

1.LHead,LTail用来存储小于基准值的。

2.RHead,RTail用来存储大于或等于基准值的。

假如链表如图：

代码如下：

 1 public class PartitionLinkNode {
 2 
 3     public static void main(String[] args) {
 4         int number[]= {5,6,3,2,1};
 5         ListNode head=new ListNode();
 6         ListNode p=head;
 7         //数组数据用链表的方式串连
 8         for(int i=0;i<number.length;i++)
 9         {
10             p.data=number[i];
11             if(!(i+1==number.length))
12             p=p.next=new ListNode();
13         }
14         
15         ListNode head2=Partition(head,3);
16         ListNode p2=head2;
17         //遍历输出
18         while(p2!=null)
19         {
20             System.out.print(p2.data+" ");
21             p2=p2.next;
22         }
23         
24     }
25     
26     public static ListNode Partition(ListNode pHead,int n) {
27         ListNode p=pHead;
28         ListNode LHead=null; //小于基准数的头结点
29         ListNode LTail=null; //小于基准数的尾结点
30         ListNode RHead=null; //大于或等于基准数的头结点
31         ListNode RTail=null; //大于或等于基准数的尾结点
32         while(p!=null)
33         {
34             int pValue=p.data;
35             if(pValue<n)
36             {
37                 if(LHead==null)
38                 {
39                     LHead=LTail=p;
40                 }else
41                 {
42                     LTail.next=p;
43                     LTail=LTail.next;
44                 }
45             }else {
46                 if(RHead==null)
47                 {
48                     RHead=RTail=p;
49                 }else
50                 {
51                     RTail.next=p;
52                     RTail=RTail.next;
53                 }
54             
55             }
56             p=p.next;
57         }
58         
59         if(LHead==null)
60         {
61             RTail.next=null;
62             return RHead;
63         }else {
64             LTail.next=RHead;
65             RTail.next=null; //注意这里需要让RTail的next为空,不然会无限循环
66         }
67         return LHead;
68 
69     }
70 }
71     //结点类
72     class ListNode {
73         int data;
74         ListNode next;
75         
76         public ListNode() {}
77         public ListNode(int data)
78         {
79             this.data=data;
80         }
81     }