Insertion Sort List,Merge Two Sorted Lists,Sort Li

Brenner 發(fā)布于2019-08-16 10:27 / 1011人閱讀

摘要：解題思路題目很簡(jiǎn)單，就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個(gè)新的元素，將其插入到前面已經(jīng)排好序的元素中。但要注意我們要將的前一個(gè)節(jié)點(diǎn)記錄下來在找到中點(diǎn)后，我們要將這樣鏈表才能分割成個(gè)。

Insertion Sort List
Sort a linked list using insertion sort.

1.解題思路

題目很簡(jiǎn)單，就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個(gè)新的元素，將其插入到前面已經(jīng)排好序的元素中。
因?yàn)轭^結(jié)點(diǎn)沒法確定，所以我們用一個(gè)dummy節(jié)點(diǎn)；然后開始向后逐個(gè)遍歷，當(dāng)前遍歷的節(jié)點(diǎn)為cur,另外sortnode每次都指向已經(jīng)排好序的第一個(gè)節(jié)點(diǎn)dummy,然后從dummy開始往后，直到找到sortnode.next.val>=cur.val,則表示cur節(jié)點(diǎn)要插到有序鏈表的sortnode后面。

2.代碼

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        ListNode cur=head;
        while(cur!=null){
            ListNode sortnode=dummy;
            while(sortnode.next!=null&&sortnode.next.val
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
1.解題思路
合并兩個(gè)有序鏈表，同樣需要構(gòu)造一個(gè)Dummy節(jié)點(diǎn)。
1）考慮特殊情況，如果有一個(gè)鏈表為空，則直接返回另一個(gè)鏈接；
2）利用兩個(gè)指針p,q遍歷兩個(gè)鏈表,如果都不為空，則循環(huán)繼續(xù)；
3）使用node指向新鏈表的最后一個(gè)節(jié)點(diǎn)，初始化為dummy
4) 比較p,q的數(shù)值的大小，如果p小于q,則把p加到node.next,并且node賦值為p,而p指針需要前進(jìn)一個(gè)；
5) 結(jié)束循環(huán)時(shí)，check一下是否還有鏈表中有剩余元素，并將剩余元素加入到新鏈表node指針的后面。
2.代碼
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
1.解題思路
題目要求時(shí)間復(fù)雜度為O(n log n)，所以我們就想到用歸并排序，自然就想到和上一題的mergeTwoLists。
但要做mergeTwoLists，必須得先將當(dāng)前的list分割成兩個(gè)List,所以采用遞歸實(shí)現(xiàn)。
要分割鏈表，最簡(jiǎn)單的辦法就是找到中點(diǎn)，那很明顯是利用slow,fast來實(shí)現(xiàn)，最后slow就是鏈表的中間點(diǎn)。但要注意我們要將Slow的前一個(gè)節(jié)點(diǎn)記錄下來pre,在找到中點(diǎn)后，我們要將pre.next=null,這樣鏈表才能分割成2個(gè)。
2.代碼
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode slow=head,fast=head,pre=null;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        return mergeTwoSortedList(l1,l2);
    }
    private ListNode mergeTwoSortedList(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val