对链表进行插入排序,
从链表第一个元素开始可以视为部分已排序,每次操作从链表中移除一个元素,然后原地将移除的元素插入到已排好序的部分。
数据范围:链表长度满足 ,链表中每个元素满足
例如输入{2,4,1}时,对应的返回值为{1,2,4},转换过程如下图所示:
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode insertionSortList (ListNode head) { if (head == null || head.next == null) { return head; } ListNode dummyHead = new ListNode(0); ListNode curr = head; while (curr != null) { ListNode next = curr.next; ListNode orderpre = dummyHead; ListNode ordercurr = dummyHead.next; while (ordercurr != null && ordercurr.val <= curr.val) { orderpre = ordercurr; ordercurr = ordercurr.next; } curr.next = orderpre.next; orderpre.next = curr; curr = next; } return dummyHead.next; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode insertionSortList (ListNode head) { // write code here ListNode dummyHead = new ListNode(-10001); while (head != null) { ListNode temp = head.next; head.next = null; insertNode(dummyHead, head); head = temp; } return dummyHead.next; } public void insertNode(ListNode dummyHead, ListNode node) { ListNode prev = dummyHead; ListNode cur = dummyHead.next; while (cur != null) { if (node.val < cur.val) { prev.next = node; node.next = cur; return; } prev = cur; cur = cur.next; } prev.next = node; } }
import java.util.*; public class Solution { //从头插入和从中间插入和从尾部插入都是不一样的 public ListNode insertionSortList (ListNode head) { // 设置一个pre指针 ListNode pre=head; head=head.next; pre.next=null; //左边已排序的链表形成 boolean flag=true; //用于标记右边链表的当前节点是否已经插入 while(head!=null){ flag=true; ListNode next=head.next; head.next=null; //从链表中移除 if(head.val<=pre.val){ //从左边链表头插入 head.next=pre; pre=head; flag=false; //如果从头节点就已经插入,把标志赋值为flase } ListNode pcur=pre; ListNode cur=pre.next; //从排序的链表头节点开始 while(flag&&cur!=null ){ //如果在中间插入,需要两个节点 if(head.val<=cur.val){ pcur.next=head; pcur=head; pcur.next=cur; flag=false; break; } cur=cur.next; pcur=pcur.next; } //如果走到尾部依然还没有插入,就把这个节点插入尾部 if(flag){ pcur.next=head; } //节点插入完毕,进行下一个节点 head=next; } return pre; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode insertionSortList (ListNode head) { // write code here if(head == null || head.next == null) return head; ListNode sortedHead = head; // 有序部分边界(降序) ListNode waitingForSort = head.next; // 待排序部分头结点 head.next = null; // 有序和待排序部分断开 while(waitingForSort != null){ if(waitingForSort.val >= sortedHead.val){ ListNode newHead = waitingForSort; waitingForSort = waitingForSort.next; // 待排序的下一个节点 newHead.next = sortedHead; sortedHead = newHead; }else{ ListNode prev = null; ListNode cur = sortedHead; // 待排序部分小于有序部分的结点就不断往后换 while(cur != null && waitingForSort.val < cur.val){ prev = cur; cur = cur.next; } if(cur != null){ // 中间找到了某个位置可以插入,待排序节点插入在prev和cur之间 ListNode newNode = waitingForSort; waitingForSort = waitingForSort.next; newNode.next = cur; prev.next = newNode; }else{ ListNode newTail = waitingForSort; prev.next = newTail; waitingForSort = waitingForSort.next; newTail.next = null; } } } return reverseList(sortedHead); } private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }
import java.util.*; public class Solution { public ListNode insertionSortList (ListNode head) { if(head == null || head.next == null){ return head; } ListNode node = insertionSortList(head.next); ListNode p = node, pre =null; while(p != null){ if(p.val < head.val){ pre = p; p = p.next; } else{ break; } } if(pre == null){ head.next = p; return head; } head.next = p; pre.next = head; return node; } }