链表经典面试题(四)

1.题目

2.详细的图文分析

我们会定义4个指向分割链表的指向指针,分别来表示两个链表的头和尾
并且将数据一一的放到两个链表中,最后再将它们串起来,代码中有详细注释.

3.详细的注释和代码

public class Partition {
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;
        }
       //定义一个cur,用来遍历链表
       ListNode cur = head;
       //定义4个指向指针,来指向分割的链表
       ListNode bs = null;
       ListNode be = null;
       ListNode as = null;
       ListNode ae = null;
       //用cur来遍历链表
       while(cur != null){
         if(cur.val < x){
            //我们用be,bs来指向小于x的链表
            //用ae,as来指向大于x的链表
            //如果bs为空的话
            if(bs == null){
                bs = cur;
                be = cur;
            }
            else{
                be.next = cur;
                be = be.next;
            }
         }
         else{
             //如果as为空
             if(as == null){
                as = cur;
                ae = cur;
             }
             else{
                ae.next = cur;
                ae = ae.next;
             }
         }
         cur = cur.next;
       }
       //出循环后,说明cur为空了,走完了整个链表
       //我们需要将两个分割的链表串联起来
       //1.如果特殊情况下,bs为空
       if(bs == null){
        return as;
       }
       //如果没走if,说明bs里面有数据
       be.next = as;
       //2.如果as不为空
       if(as != null){
        //保证链表的最后一个数据的next域为空
        ae.next = null;
       }
       return bs;
    }
}
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

分割链表的题目非常难,需要各位好好考虑清楚各种情况,希望大家好好看博主的图和代码,数据结构不画图的话是学不会的