代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。
插入排序算法:
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
遍历链表,每次将遍历到的结点 cur 与前一个结点 pre 进行值比较:
依次遍历,直至 cur 指向空,遍历结束。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(head.val)
dummy.next = head
pre, cur = dummy, head
while cur:
if pre.val <= cur.val:
pre, cur = cur, cur.next
continue
p = dummy
while p.next.val <= cur.val:
p = p.next
t = cur.next
cur.next = p.next
p.next = cur
pre.next = t
cur = t
return dummy.next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(head.val);
dummy.next = head;
ListNode pre = dummy, cur = head;
while (cur != null) {
if (pre.val <= cur.val) {
pre = cur;
cur = cur.next;
continue;
}
ListNode p = dummy;
while (p.next.val <= cur.val) {
p = p.next;
}
ListNode t = cur.next;
cur.next = p.next;
p.next = cur;
pre.next = t;
cur = t;
}
return dummy.next;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。