讨论/《排序算法全解析》 - 147. 对链表进行插入排序/
《排序算法全解析》 - 147. 对链表进行插入排序
共 9 个回复

C++插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //定义伪节点
        ListNode *wei = new ListNode(), *tmp = head;
        //遍历原链表,插入到已排序链表中
        while(tmp){
            //存储原链表下一个节点
            ListNode *nxt = tmp -> next;
            //从已排序链表中找到插入点
            head = wei;
            while(head -> next && head -> next -> val < tmp -> val)
                head = head -> next;
            //修改两个节点指针
            tmp -> next = head -> next;
            head -> next = tmp;
            //tmp赋值为下一个原链表节点,准备下一轮迭代
            tmp = nxt;
        }
        return wei -> next;
    }
};
3
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode last = head, curr = head.next;
        while (curr != null) {
            if (last.val <= curr.val) {
                last = last.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) prev = prev.next;
                last.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = last.next;
        }
        return dummyHead.next;
    }
}
3

四个月前做过的题目,忘记了,再重做一遍。哑节点针不戳。
Python

def insertionSortList(head):
    dummyNode = ListNode()
    dummyNode.next = head
    sorted_last = head
    curr = head.next
    while curr:
        pre = dummyNode
        if curr.val >= sorted_last.val:
            curr = curr.next
            sorted_last = sorted_last.next
            continue
        while pre:
            if pre.next.val <= curr.val:
                pre = pre.next
            else:
                sorted_last.next = curr.next
                curr.next = pre.next
                pre.next = curr
                break
        curr = sorted_last.next
    return dummyNode.next
1

C++ 链表插入排序

本题最优解是归并排序。lc 上有题目。

链表题目其实很简单的,无非就是拆节点,然后重建链表。只有明白这两点,相信在座各位不会被指针搞得头大了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy;  // 新链表虚拟头节点
        while (head) {
            // (1) 拆当前 head 节点
            ListNode *nxt = head->next;
            // (2) 在新链表中寻找插入位置(前驱)
            ListNode *prev = &dummy;
            while (prev->next && prev->next->val <= head->val) prev = prev->next;
            // (3) 将 head 插在 prev 之后
            head->next = prev->next;
            prev->next = head;
            prev = head;

            head = nxt;  // 继续遍历原链表剩余节点
        }
        return dummy.next;
    }
};
1
//方法1
func insertionSortList(head *ListNode) *ListNode {
    dump:=&ListNode{-1,nil}
    temp:=dump
    for head!=nil{
        p:=dump
        for p.Next!=nil&&p.Next.Val<head.Val{
            p=p.Next
        }
        temp,p.Next=p.Next,head
        head,p.Next.Next=head.Next,temp
    }
    return dump.Next
}

//方法2
func insertionSortList(head *ListNode) *ListNode {
	dummy := &ListNode{-1, head}
	for head != nil && head.Next != nil {
		if head.Val <= head.Next.Val {
			head = head.Next
			continue
		}
		temp, prev := head.Next, dummy
		head.Next = head.Next.Next
		for prev.Next.Val < temp.Val {
			prev = prev.Next
		}
		temp.Next, prev.Next = prev.Next, temp
	}
	return dummy.Next
}
1

C++ %5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) 
    {
        if(!head) return nullptr;
        ListNode* phead = new ListNode(-1,head);
        auto pcur = head->next;
        while(pcur)
        {
            if(head->val < pcur->val && head->next != pcur)
            {
                head = head->next;
            }
            else if(head->val >= pcur->val 
            && head->next != pcur)
            {
                swap(pcur->val,head->val);
                head = head->next;
            }
            else if( head->val < pcur->val 
            && head->next == pcur)
            {
                pcur = pcur->next;
                head = phead->next;
            }
            else
            {
                swap(pcur->val,head->val);
                pcur = pcur->next;
                head = phead->next;
            }
        }

        return phead->next;
    }
};
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head==nullptr || head->next == nullptr){
            return head;
        }
        ListNode*p=nullptr,*q=nullptr;
        for(p =head->next;p!=nullptr;p=p->next){
            for(q=head;q!=p;q=q->next){
                if(p->val<q->val){
                    int temp=q->val;
                    q->val=p->val;
                    p->val=temp;
                }
            }
        }
        return head;
    }
};

递归版本

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode p = head;
        ListNode res = null;
        while(p != null){
            ListNode q = p.next;
            res = insert(res, p);
            p = q;
        }
        return res;
    }

    private ListNode insert(ListNode head, ListNode node){
        node.next = null;
        if(head == null){
            return node;
        }

        if(node.val < head.val){
            node.next = head;
            return node;
        }
        head.next = insert(head.next, node);
        return head;
    }
}

C++

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *Head=new ListNode(0),*pre_head=Head;
        Head->next=head;
        while(head)
        {
            bool changed=false;
            auto pre=Head,cur=Head->next;
            while(cur!=head)
            {
                if(head->val<cur->val)
                {
                    pre_head->next=head->next;
                    pre->next=head;
                    head->next=cur;
                    head=pre_head->next;
                    changed=true;
                    break;
                }
                pre=pre->next;
                cur=cur->next;
            }
            if(!changed)
            {
                head=head->next;
                pre_head=pre_head->next;
            }
            
        }
        return Head->next;
    }
};