<ul id="yaqcu"></ul>

劍指offer:合并兩個排序的鏈表（Java）

darkbaby123 發布于2019-08-16 18:39 / 764人閱讀

摘要：問題描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

1.問題描述

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

2.思路

方法1:非遞歸方法

根據題目這個很類似排序中的外排過程,兩個數組分別排好序,然后再把他們整體進行排序.所以這道題思想很簡單,就是用兩個變量分別遍歷兩個鏈表.比較遍歷到的兩個節點的值,小的節點就斷開與后面的連接,連到遍歷到的另一個節點上,同時讓小的節點向后移動一位,大節點位置不變,所以這里需要一個變量來記錄值較小的節點后面一個節點,保證斷開與后面的連接后可以獲得后面的節點.這樣執行循環操作,直到一個鏈表循環到最后停止.就會把兩個鏈表合成一個有序的新鏈表.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)    //判斷鏈表1是否為null,如果為null,直接返回鏈表2.
            return list2;
        else if(list2 == null)    //判斷鏈表2是否為null.
            return list1; 
        ListNode pNode1 = list1;    //記錄鏈表1的頭節點,因為要返回新的鏈表,所以最后比較一下返回值較小的頭節點
        ListNode pNode2 = list2;    //記錄鏈表2的頭節點  
        ListNode next = null;    //小節點斷開與后面的連接時用于記錄小節點后面的一個節點,保證能遍歷到。
        while(list1 != null && list2 != null){    //只要有一個鏈表到最后就停止循環
            if(list1.val <= list2.val){    //較小的節點連到大節點上
                next = list1.next;
                list1.next = list2;
                list1 = next;
            } else{
                next = list2.next;
                list2.next = list1;
                list2 = next;
            }
        }
        return pNode1.val <= pNode2.val ? pNode1 : pNode2;    //返回兩個頭節點中較小的那個.
    }
}

方法2:遞歸方法

關鍵就是判斷list1和list2的val值的大小,然后改變list1或list2的next的指向.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next,list2);    
            //這里是改變list1的next的指向,里面填list1.next是為了讓list1的節點向后移動一位.
            return list1;
        }else{
            list2.next = Merge(list2.next,list1);
            return list2;
        }
    }
}

遞歸方法參考牛客網:披薩大叔的方法

GPU云服務器云服務器鏈表排序合并鏈表的c語言鏈表排序算法合并排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/75505.html

PHPer也刷《劍指Offer》之鏈表

摘要：劍指中鏈表相關題目俗話說光說不練假把式，既然學習了鏈表的基礎概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關題目。題目分析合并兩個排序的鏈表，需要分別比較兩個鏈表的每個值，然后改變指針。溫故知新鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。根據類型可以分為單鏈表、雙鏈表、環形鏈表、...

daydream 2019-07-01 10:11 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
《劍指offer》分解讓復雜問題更簡單

摘要：拆分鏈表，將和進行拆分，保證原始鏈表不受影響。要求不能創建任何新的結點，只能調整樹中結點指針的指向。輸入一個字符串長度不超過可能有字符重復字符只包括大小寫字母。遞歸，記錄一個當前節點的位置，該位置指向最后一個節點時記錄一次排列。 1.復雜鏈表的復制輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的hea...

wawor4827 2019-08-23 15:27 評論0 收藏0