Java对LinkedList进行排序

Love The Way You Lie 2023-10-05 21:25 1阅读 0赞

[链表][Link 1]是一个线性数据结构，其中的元素是不能存储在连续的存储单元。

**按升序对单链接列表的节点进行排序：**

![原始清单][4afdeb90fe05760dfb9f84b7dc5b5eb8.png]

*原始清单*

![SortedList][]

*排序清单*

**我们可以通过许多排序技术对LinkedList进行排序：**

1.  气泡排序
2.  插入排序
3.  快速分类
4.  合并排序

**方法1：使用**[**冒泡排序进行排序**][Link 2]

*  为了完成此任务，我们维护两个指针：current和index。
 *  最初，当前指向头节点，索引将指向当前旁边的节点。
 *  通过将当前数据与索引数据进行比较，遍历列表直到当前指向null。
 *  对于每个当前值，索引是当前节点的下一个节点，它从当前的下一个节点开始遍历直到为空。
 *  然后，将当前节点的值与从其下一个节点到最后一个节点的每个值进行比较，如果该值小于当前值，则将交换这些值，并以这种方式将最小值作为当前索引。

### 爪哇 ###

*filter\_none*

*编辑*

*play\_arrow*

*亮度\_4*

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:528px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program to sort a Linked List using Bubble Sort </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>class</code> <code>SortList { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Represent a node of the singly linked list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>class</code> <code>Node { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>Node(</code><code>int</code> <code>data) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.data = data; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.next = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Represent the head and tail of the singly linked list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>Node head = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>Node tail = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// addNode() will add a new node to the list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>void</code> <code>addNode(</code><code>int</code> <code>data) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Create a new node </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node newNode = </code><code>new</code> <code>Node(data); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Checks if the list is empty </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// If list is empty, both head and tail will </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// point to new node </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = newNode; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>tail = newNode; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code> <code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// newNode will be added after tail such that </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// tail's next will point to newNode </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>tail.next = newNode; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// newNode will become new tail of the list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>tail = newNode; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// sortList() will sort nodes of the list in ascending </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// order </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>void</code> <code>sortList() </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Node current will point to head </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node current = head, index = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>temp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code> <code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(current != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Node index will point to node next to </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// current </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index = current.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(index != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// If current node's data is greater </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// than index's node data, swap the data </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// between them </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(current.data &gt; index.data) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = current.data; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current.data = index.data; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index.data = temp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index = index.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current = current.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// display() will display all the nodes present in the </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>void</code> <code>display() </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Node current will point to head </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node current = head; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"List is empty"</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(current != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Prints each node by incrementing pointer </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(current.data + </code><code>" "</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current = current.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>SortList sList = </code><code>new</code> <code>SortList(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Adds data to the list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.addNode(</code><code>8</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.addNode(</code><code>3</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.addNode(</code><code>7</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.addNode(</code><code>4</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Displaying original list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Original list: "</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.display(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Sorting list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.sortList(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Displaying sorted list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Sorted list: "</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sList.display(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**输出**

原始清单： 
    8 3 7 4 
    排序列表： 
    3 4 7 8

**时间复杂度：** O（n ^ 2）

**空间复杂度：** O（1）

**方法2：使用**[**插入排序进行排序**][Link 3]

*  在插入排序技术中，我们假定列表中当前元素之前的所有元素均已排序，并且我们从当前元素开始。
 *  将当前元素与其之前的所有元素进行比较，如果不按顺序交换，则将其交换。对所有后续元素重复此过程。
 *  通常，插入排序技术会将每个元素与其所有先前的元素进行比较，并对元素进行排序以将其放置在适当的位置。

如前所述，插入排序技术对于较小的数据集更可行，因此可以使用有效的插入排序对具有少量元素的数组进行排序。

插入排序在对链表数据结构进行排序时特别有用。如您所知，链接列表的指针指向其下一个元素（单链接列表）和上一个元素（双链接列表）。这样可以更轻松地跟踪上一个和下一个元素。

### 爪哇 ###

*filter\_none*

*编辑*

*play\_arrow*

*亮度\_4*

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:653px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program to sort Linked List using Insertion Sort&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>class</code> <code>LinkedlistIS&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node sorted;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>class</code> <code>node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>val;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>node(</code><code>int</code> <code>val)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.val = val;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>push(</code><code>int</code> <code>val)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// allocate node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node newnode = </code><code>new</code> <code>node(val); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// link the old list off the new node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>newnode.next = head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// move the head to point to the new node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = newnode;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// function to sort a singly linked list using insertion sort&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>insertionSort(node headref)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Initialize sorted linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sorted = </code><code>null</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node current = headref;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Traverse the given linked list and insert every&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// node to sorted&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(current != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Store next for next iteration&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node next = current.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// insert current in sorted linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sortedInsert(current);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Update current&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current = next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Update head_ref to point to sorted linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = sorted;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// function to insert a new_node in a list. Note that&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// this function expects a pointer to head_ref as this&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// can modify the head of the input linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// (similar to push())&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>sortedInsert(node newnode)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Special case for the head end&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(sorted == </code><code>null</code> <code>|| sorted.val &gt;= newnode.val)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>newnode.next = sorted;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sorted = newnode;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node current = sorted;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Locate the node before the point of insertion&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(current.next != </code><code>null</code> <code>&amp;&amp; current.next.val &lt; newnode.val)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current = current.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>newnode.next = current.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current.next = newnode;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Function to print linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>printlist(node head)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(head != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(head.val + </code><code>" "</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = head.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Driver program to test above functions&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>LinkedlistIS list = </code><code>new</code> <code>LinkedlistIS();&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.push(</code><code>4</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.push(</code><code>7</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.push(</code><code>3</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.push(</code><code>8</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Linked List before Sorting.."</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printlist(list.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.insertionSort(list.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"\nLinkedList After sorting"</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printlist(list.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**输出**

排序前的链表
    8 3 7 4 
    排序后的LinkedList
    3 4 7 8

**时间复杂度：** O（n ^ 2）

**空间复杂度：** O（1）

**方法3：使用**[**快速排序进行排序**][Link 4]

快速分类遵循[分而治之的][Link 5]方法。它选择一个元素作为枢轴，并围绕拾取的枢轴对给定的数组进行分区。

quickSort中的关键过程是partition（）。分区的目标是，给定一个数组和一个数组元素x作为枢轴，将x放在排序数组中的正确位置，并将所有较小的元素（小于x）放在x之前，并将所有较大的元素（大于x）放在之后X。所有这些都应在线性时间内完成。

快速排序优先于合并排序，因为快速排序是一种就地算法（意味着不需要额外的存储空间）。

### 爪哇 ###

*filter\_none*

*编辑*

*play\_arrow*

*亮度\_4*

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:512px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program for Quick Sort on Singly Linked List&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>class</code> <code>QuickSortLinkedList&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>class</code> <code>Node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node(</code><code>int</code> <code>d)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.data = d;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.next= </code><code>null</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>Node head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>void</code> <code>addNode(</code><code>int</code> <code>data)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(head == </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = </code><code>new</code> <code>Node(data);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node curr = head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(curr.next != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr = curr.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node newNode = </code><code>new</code> <code>Node(data);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr.next = newNode;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>void</code> <code>printList(Node n)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(n != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(n.data);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>" "</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>n = n.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// takes first and last node,&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// but do not break any links in&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// the whole linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>Node paritionLast(Node start, Node end)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(start == end ||&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>start == </code><code>null</code> <code>|| end == </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>start;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node pivot_prev = start;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node curr = start;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>pivot = end.data;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// iterate till one before the end,&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// no need to iterate till the end&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// because end is pivot&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(start != end )&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(start.data &lt; pivot)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// keep tracks of last modified item&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>pivot_prev = curr;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>temp = curr.data;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr.data = start.data;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>start.data = temp;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr = curr.next;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>start = start.next;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// swap the position of curr i.e.&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// next suitable index and pivot&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>temp = curr.data;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr.data = pivot;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end.data = temp;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// return one previous to current&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// because current is now pointing to pivot&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>pivot_prev;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>void</code> <code>sort(Node start, Node end)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(start == end )&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// split list and partion recurse&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node pivot_prev = paritionLast(start, end);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sort(start, pivot_prev);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// if pivot is picked and moved to the start,&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// that means start and pivot is same&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// so pick from next of pivot&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>( pivot_prev != </code><code>null</code> <code>&amp;&amp;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>pivot_prev == start )&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sort(pivot_prev.next, end);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// if pivot is in between of the list,&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// start from next of pivot,&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// since we have pivot_prev, so we move two nodes&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code> <code>if</code><code>(pivot_prev != </code><code>null</code> <code>&amp;&amp;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>pivot_prev.next != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sort(pivot_prev.next.next, end);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Driver Code&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>QuickSortLinkedList list = </code><code>new</code> <code>QuickSortLinkedList();&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.addNode(</code><code>8</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.addNode(</code><code>3</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.addNode(</code><code>7</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.addNode(</code><code>4</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node n = list.head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(n.next != </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>n= n.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Original List: "</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(list.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.sort(list.head , n);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"\nSorted List: "</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(list.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**输出**

原始清单： 
    8 3 7 4 
    排序列表： 
    3 4 7 8

**时间复杂度：** O（n ^ 2）

**空间复杂度：** O（1）

**方法3：使用**[**合并排序**][Link 6]

合并排序通常是对链表进行排序的首选。链表的随机访问性能较慢，使得其他一些算法（例如quicksort）的性能较差，而其他算法（例如堆排序）则完全不可能。

合并排序是一种[分而治之][Link 7]算法。它将输入数组分为两个半部分，将自身称为两个半部分，然后合并两个已排序的半个部分。**merge（）函数**用于合并两个半部分。merge（arr，l，m，r）是一个关键过程，假定对arr \[l..m\]和arr \[m + 1..r\]进行排序并将两个排序后的子数组合并为一个。

*  令head是要排序的链表的第一个节点，而headRef是指向head的指针。
 *  请注意，我们需要在MergeSort（）中引用head，因为以下实现会更改下一个链接以对链接列表进行排序（而不是节点上的数据），因此如果原始head上的数据不是最小值，则必须更改head节点。在链接列表中。

### 爪哇 ###

*filter\_none*

*编辑*

*play\_arrow*

*亮度\_4*

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:536px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program to sort linkedList using Merge Sort </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>class</code> <code>linkedList&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node head = </code><code>null</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// node a, b;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>class</code> <code>node {&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>val;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>node(</code><code>int</code> <code>val)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.val = val;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node sortedMerge(node a, node b)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node result = </code><code>null</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Base cases&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(a == </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>b;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(b == </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>a;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Pick either a or b, and recur&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(a.val &lt; b.val) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result = a;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result.next = sortedMerge(a.next, b);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result = b;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result.next = sortedMerge(a, b.next);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>result;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node mergeSort(node h)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Base case : if head is null&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(h == </code><code>null</code> <code>|| h.next == </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>h;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// get the middle of the list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node middle = getMiddle(h);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node nextofmiddle = middle.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// set the next of middle node to null&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>middle.next = </code><code>null</code><code>;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Apply mergeSort on left list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node left = mergeSort(h);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Apply mergeSort on right list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node right = mergeSort(nextofmiddle);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Merge the left and right lists&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node sortedlist = sortedMerge(left, right);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>sortedlist;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Utility function to get the middle of the linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>node getMiddle(node head)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node slow = head, fast = head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(fast.next != </code><code>null</code> <code>&amp;&amp; fast.next.next != </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>slow = slow.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>fast = fast.next.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>slow;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>push(</code><code>int</code> <code>new_data)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// allocate node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node new_node = </code><code>new</code> <code>node(new_data);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// link the old list off the new node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>new_node.next = head;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// move the head to point to the new node&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = new_node;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Utility function to print the linked list&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>printList(node headref)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(headref != </code><code>null</code><code>) {&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(headref.val + </code><code>" "</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>headref = headref.next;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>linkedList li = </code><code>new</code> <code>linkedList();&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.push(</code><code>4</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.push(</code><code>7</code><code>);&nbsp;&nbsp;&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.push(</code><code>3</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.push(</code><code>8</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"\nOriginal List: \n"</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.printList(li.head); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Apply merge Sort&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.head = li.mergeSort(li.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"\nSorted List: \n"</code><code>);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>li.printList(li.head);&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}&nbsp; </code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**输出**

原始清单： 
    8 3 7 4 
    排序列表： 
    3 4 7 8

**时间复杂度：** O（n log n）

**空间复杂度：** O（1）

[Link 1]: https://www.geeksforgeeks.org/data-structures/linked-list/
[4afdeb90fe05760dfb9f84b7dc5b5eb8.png]: https://img-blog.csdnimg.cn/img_convert/4afdeb90fe05760dfb9f84b7dc5b5eb8.png
[SortedList]: https://img-blog.csdnimg.cn/img_convert/b70bd7170a94e3c3eb45c13973e5add2.png
[Link 2]: https://www.geeksforgeeks.org/bubble-sort/
[Link 3]: https://www.geeksforgeeks.org/insertion-sort-for-singly-linked-list/
[Link 4]: https://www.geeksforgeeks.org/quick-sort/
[Link 5]: https://www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/
[Link 6]: https://www.geeksforgeeks.org/merge-sort/
[Link 7]: https://www.geeksforgeeks.org/divide-and-conquer-introduction/