Java中有序单链表的构建

1、解析

每次创建一个新的结点时，要想让我们的链表保持一个有序的状态，那么就是得每次插入新结点都得去和链表的结点去比较。

以下以int值的链表升序排列为例，将会出现以下情况：

1. 此时头节点为空，则可以直接插入，

       public void orderLink(int value){
           ListNode node=new ListNode(value);
           if(head==null){
               head=node;
               return;
           }
       }
   1
   2
   3
   4
   5
   6
   7

2. 如果头节点不为空，此时的value值小于头节点，那么可以直接插入最前面，该节点当为头节点

   if(value< head.value){
          node.next=head;
          head=node;
          return;
   }
   1
   2
   3
   4
   5

3. 如果该结点的大小在链表的两个结点之间

此时我们需要将node结点放入到两个结点之间：

node.next=indexNode;
preNode.next=node;
1
2

2、整体代码实现

    /**
     * 有序单链表的构建
     */
    public void orderLink(int value){
        ListNode node=new ListNode(value);
        if(head==null){
            head=node;
            return;
        }
        if(value< head.value){
            node.next=head;
            head=node;
            return;
        }
        ListNode indexNode=head;
        ListNode preNode=indexNode;
        while (true){
            if(indexNode==null){
                preNode.next=node;
                return;
            }
            if(value> indexNode.value){
                preNode=indexNode;
                indexNode=indexNode.next;
            }else{
                node.next=indexNode;
                preNode.next=node;
                return;
            }
        }
    }
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