对链表进行插入排序,
从链表第一个元素开始可以视为部分已排序,每次操作从链表中移除一个元素,然后原地将移除的元素插入到已排好序的部分。
数据范围:链表长度满足 ,链表中每个元素满足
例如输入{2,4,1}时,对应的返回值为{1,2,4},转换过程如下图所示:
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* insertionSortList(ListNode* head) { // write code here ListNode* p = head; while(p->next) { // 去找到这个比前一个值小的结点位置 while(p->next && p->next->val > p->val) p = p->next; // 如果为空 则 返回 if(p->next == nullptr) return head; // 如果不为空 则 找到异常值 位置 选择合适的位置进行插入 ListNode* tmp = new ListNode(p->next->val); // 加入比头结点小,直接插到头结点位置 if(tmp->val < head->val) { tmp->next = head; head = tmp; } // 否则找到合适的位置插入 else { // 从头结点位置开始找到合适的位置 ListNode* t = head; // 插入的位置的值 一定是比前一个值大 while(t->next && t->next->val < tmp->val) t = t->next; // 插入操作 tmp->next = t->next; t->next = tmp; } // 跳过被插入的位置,因为已经有序了 p->next = p->next->next; } return head; } };
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; } }
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def insertionSortList(self , head: ListNode) -> ListNode: # write code here res = ListNode(0) point = head while point is not None: point_next = point.next insert = res while insert is not None: if insert.next is None: insert.next = point point.next = None break # 寻找插入位置 if point.val > insert.next.val: insert = insert.next continue else: tmp = insert.next insert.next = point point.next = tmp break point = point_next return res.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; } }
/** * #[derive(PartialEq, Eq, Debug, Clone)] * pub struct ListNode { * pub val: i32, * pub next: Option<Box<ListNode>> * } * * impl ListNode { * #[inline] * fn new(val: i32) -> Self { * ListNode { * val: val, * next: None, * } * } * } */ struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ pub fn insertionSortList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // write code here // let mut ordered_num = 0; let mut dummy_head_new = Some(Box::new(ListNode::new(233))); let mut dummy_head = Some(ListNode::new(233)); dummy_head.as_mut()?.next = head; // let ordered_list = None; let mut p = &mut dummy_head; while p.as_ref()?.next.is_some() { let mut node = p.as_mut()?.next.take(); p.as_mut()?.next = node.as_mut()?.next.take(); let mut p_insert_next = &mut dummy_head_new; while p_insert_next.as_ref()?.next.is_some() && p_insert_next.as_ref()?.next.as_ref()?.val <= node.as_ref()?.val { p_insert_next = &mut p_insert_next.as_mut()?.next; } node.as_mut()?.next = p_insert_next.as_mut()?.next.take(); p_insert_next.as_mut()?.next = node; } // todo!(); dummy_head_new?.next } }
struct ListNode* insertionSortList(struct ListNode* head ) { if(head==NULL) return NULL; struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; struct ListNode *p = dummy->next->next; struct ListNode *q = dummy; struct ListNode *cur = dummy->next; while(p!=NULL) { while(q->next!=p) { if(q->next->val>p->val) { cur->next = p->next; p->next = q->next; q->next = p; break; } q = q->next; } cur = p; p = p->next; q = dummy; } return dummy->next; }
package main import "sort" import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ func insertionSortList( head *ListNode ) *ListNode { arr:=[]*ListNode{} for p:=head;p!=nil;p=p.Next{ arr=append(arr,p) } sort.Slice(arr,func(i,j int)bool{ return arr[i].Val<arr[j].Val }) for i,p:=range arr{ if i+1<len(arr){ p.Next=arr[i+1] }else{ p.Next=nil } } return arr[0] }
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 ListNode dummy=new ListNode(-1); ListNode tail=dummy; for(;head!=null;){ ListNode tmp1=head.next; for(ListNode i=dummy;i!=null;i=i.next){ if(i.next!=null&&i.next.val>=head.val){ head.next=i.next; i.next=head; break; }else if(i.next==null){ i.next=head; tail=head; tail.next=null; break; } } head=tmp1; } return dummy.next; } }
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 Solution { public ListNode insertionSortList (ListNode head) { if(head == null || head.next == null) return head; ListNode headNode = new ListNode(-1); headNode.next = head; ListNode cur = head.next; ListNode lastNode = head; while(cur != null) { if(cur.val >= lastNode.val) { lastNode = lastNode.next; }else{ ListNode prev = headNode; while(prev.next.val <= cur.val) { prev = prev.next; } lastNode.next = cur.next;//删除cur节点 ListNode c = prev.next; prev.next = cur; cur.next = c;//插入节点 } cur = lastNode.next; } return headNode.next; } }
public ListNode insertionSortList (ListNode head) { int i=0,j=0,k=0; ListNode p=head; ListNode p1=head; while(p!=null){ i++; p=p.next; } int[] a=new int[i]; while(p1!=null){ a[j++]=p1.val; p1=p1.next; } Arrays.sort(a); ListNode node=head; while(head!=null){ head.val=a[k++]; head=head.next; } return node; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* insertionSortList(ListNode* head) { // write code here if(!head || !head->next) return head; typedef ListNode* list; list node = (list)malloc(sizeof(ListNode)); node->next = head; node->val = -99999; list phead = head; list p = node;//给链表增加一个头节点,以便于插入操作 list loc = nullptr; while(phead){ p = node; loc = phead->next;//当前节点的下一个节点,也是可能的排序元素 if(loc){ if(phead->val > loc->val){ //若当前元素大于后面一个元素,则将后一个元素插入到前面的有序序列中 list loc_min = nullptr;//插入点的前一个节点 while(p->val < loc->val){ loc_min = p; p = p->next; } phead->next = loc->next; loc->next = loc_min->next; loc_min->next = loc; continue; } } else//后一个节点为空,则退出循环 break; phead = phead->next; } return node->next;//应该是返回队头节点,而不是头节点 } };
class Solution: def insertionSortList(self , head: ListNode) -> ListNode: # write code here if not head: return head tmp = ListNode(0) tmp.next = head pre,cur = head,head.next while cur: if pre.val<cur.val: pre,cur = cur,cur.next continue pre.next = cur.next h = tmp while h.next.val<cur.val: h = h.next t = h.next h.next = cur cur.next = t cur = pre.next return tmp.next
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; } }