题解 | #单链表的排序#

使用冒泡排序实现单链表的排序，要定义头尾节点，方便循环，两层循环，内部进行交换

//class ListNode {
//    int val;
//    ListNode next = null;
//}

public class Solution {
    /**
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList(ListNode head) {
        if (head == null || head.next == null)  //链表为空或者仅有单个结点
            return head;
        //定义头节点和尾结点
        ListNode cur, tail = null;
        cur = head;

        //冒泡排序实现，这里两个while相当于数组排序时的双层for循环
        while (cur.next != tail) {
            while (cur.next != tail) {
                if (cur.val > cur.next.val) {
                    int tmp = cur.val;
                    cur.val = cur.next.val;
                    cur.next.val = tmp;
                }
                cur = cur.next;
            }
            //第一层循环之后，需要重新设置遍历的头尾节点
            tail = cur;  //下一次遍历的尾结点是当前结点(仔细琢磨一下里面的道道)
            cur = head;     //遍历起始结点重置为头结点
        }

        return head;
    }
}