leetcode [#147]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Sort a linked list using insertion sort.

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null) return head;
        //新建一个节点，指向头结点
        ListNode root = new ListNode(0);
        root.next = head;
        ListNode p = head;
        ListNode q;
        ListNode r;

        while (p != null && p.next != null) {
            //如果顺序升序，则不作处理，P指针后移
            if (p.val <= p.next.val) {
                p = p.next;
            }else {
                //否则断开当前节点后其后节点的连接，为p.next找到合适的位置并插入（方法是从头结点开始比大小）
                q = p.next;
                p.next = q.next;

                r = root;
                while (r.next.val <= q.val) {
                    r = r.next;
                }

                q.next = r.next;
                r.next = q;
            }
        }

        return root.next;
    }
}

---

注意事项

1. 数组的插入排序是很简单的，只需要两个循环进行遍历即可，常见的做法如下：

   public class Insertion{
   	public static void sort(a){
   		int N = a.length;
   		for(int i = 1; i< N; i++){
   			for(int j = i; j > 0 && a[j] < a[j-1]; j--){
   				int temp = a[j];
   				a[j] = a[j-1];
   				a[j-1] = temp;
   			}
   		}
   	}
   }

2. 而对于链表排序，由于链表不支持随机访问，因此这种“遍历”必须每次都从头结点开始，而不能逐一递减向前找合适的位置插入。

3. 思路是：当发现两个大小关系异常的节点—前大A后小B，首先断开两个节点的链接，将前一个节点A指向后一个节点B之后的节点。然后从链表的头结点开始到较大节点A结束这段范围内（必然在这段范围），逐一和较小节点B进行比较，当发现某节点C的下一节点已经大于较小节点B，则将B插入到C后面即可。