leetCode解题报告之Insertion Sort List

曾经终败给现在 2022-08-25 15:44 188阅读 0赞

**题目：**

Sort a linked list using insertion sort.

**分析：**

这个题目是想要让我们来做一个链表的插入排序问题.

这样，我们只要从第一个元素一直往后，直到所有的节点都在前面的序列中找到自己所在的位置即可

**情况：**

1. 当前值比head的值还小，这情况要插入到head节点之前

2. 当前值比head的值大，这情况要插入到相应的位置

3. 当前值大于所有该节点之前的值，那么当cmpNode(用来作比较的结点)和自身相等的时候，只要将当前结点(nowNode)往后挪一个结点进行下一个结点的比较即可.

**解题思路：**

大家都知道，如果要在一个位置插入一个结点，那么要知道它的前一个位置的结点才可以，所以为了满足“情况1”，我们引入一个结点preHead(head的前一个结点)，它的next域指向head。

接着引入一个 nowNode(当前结点) 和 一个 preNowNode（当前结点的前驱结点）【处于nowNode之前的那些结点是已经排好序了】

最后在引入一个cmpNode(做比较的结点) 和一个preCmpNode(正在做比较的结点的前驱结点) 【从head 直到 nowNode ，依次取出来 和 nowNode做比较，确定nowNode要插入的位置】

有了上面的这些介绍，剩下的看代码，应该就容易多了！！

附个过程图解：

![SouthEast][]

package cn.xym.leetcode;
    
    
    
    
    class ListNode {
    	public int val;
    	public ListNode next;
    
    
    	ListNode(int x) {
    		val = x;
    		next = null;
    	}
    }
    
    
    public class Solution {
    	
    	public static void main(String[] args) {
    		ListNode head = new ListNode(10);
    		ListNode head1 = new ListNode(3);
    		ListNode head2 = new ListNode(8);
    		ListNode head3 = new ListNode(22);
    		ListNode head4 = new ListNode(15);
    		ListNode head5 = new ListNode(50);
    		
    		head.next = head1;
    		head1.next = head2;
    		head2.next = head3;
    		head3.next = head4;
    		head4.next = head5;
    		head5.next = null;
    		
    		head = insertionSortList(head);
    		while (head != null){
    			System.out.println(head.val);
    			head = head.next;
    		}
    	}
    	
    	public static ListNode insertionSortList(ListNode head) {
    		if (head == null || head.next == null) {
    			return head;
    		}
    		
    		ListNode preHead = new ListNode(Integer.MIN_VALUE);
    		preHead.next = head;
    		
    		ListNode nowNode = head.next, preNowNode = head;
    		while (nowNode != null){
    			ListNode cmpNode = head;
    			ListNode precmpNode = preHead;
    			while (cmpNode != null && !cmpNode.equals(nowNode)){
    				if (cmpNode.val > nowNode.val){
    					if (cmpNode.equals(head)){
    						preNowNode.next = nowNode.next;
    						nowNode.next = preHead.next;
    						preHead.next = nowNode;
    						head = nowNode;
    						nowNode = preNowNode.next;
    					}else{
    						preNowNode.next = nowNode.next;
    						nowNode.next = precmpNode.next;
    						precmpNode.next = nowNode;
    						nowNode = preNowNode.next;
    					}
    					break;
    				}else{
    					precmpNode = cmpNode;
    					cmpNode = cmpNode.next;
    				}
    			}
    			if (cmpNode.equals(nowNode)){
    				preNowNode = nowNode;
    				nowNode = preNowNode.next;
    			}
    		}
    		return preHead.next;
    	}
    }

[SouthEast]: /images/20220824/6c6f4f6bff2a4f95a3d233bceaa5f75c.png