資訊專欄INFORMATION COLUMN
摘要：解題思路題目很簡單，就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個新的元素，將其插入到前面已經(jīng)排好序的元素中。但要注意我們要將的前一個節(jié)點記錄下來在找到中點后，我們要將這樣鏈表才能分割成個。
Insertion Sort List
Sort a linked list using insertion sort.
1.解題思路
題目很簡單，就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個新的元素，將其插入到前面已經(jīng)排好序的元素中。
因為頭結(jié)點沒法確定，所以我們用一個dummy節(jié)點；然后開始向后逐個遍歷，當(dāng)前遍歷的節(jié)點為cur,另外sortnode每次都指向已經(jīng)排好序的第一個節(jié)點dummy,然后從dummy開始往后，直到找到sortnode.next.val>=cur.val,則表示cur節(jié)點要插到有序鏈表的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òu)造一個Dummy節(jié)點。
1）考慮特殊情況，如果有一個鏈表為空，則直接返回另一個鏈接；
2）利用兩個指針p,q遍歷兩個鏈表,如果都不為空，則循環(huán)繼續(xù)；
3）使用node指向新鏈表的最后一個節(jié)點，初始化為dummy
4) 比較p,q的數(shù)值的大小，如果p小于q,則把p加到node.next,并且node賦值為p,而p指針需要前進一個；
5) 結(jié)束循環(huán)時，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.解題思路
題目要求時間復(fù)雜度為O(n log n)，所以我們就想到用歸并排序，自然就想到和上一題的mergeTwoLists。
但要做mergeTwoLists，必須得先將當(dāng)前的list分割成兩個List,所以采用遞歸實現(xiàn)。
要分割鏈表，最簡單的辦法就是找到中點，那很明顯是利用slow,fast來實現(xiàn)，最后slow就是鏈表的中間點。但要注意我們要將Slow的前一個節(jié)點記錄下來pre,在找到中點后，我們要將pre.next=null,這樣鏈表才能分割成2個。
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
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/69826.html
摘要：分治做法中，函數(shù)依然是將鏈表結(jié)點兩兩進行比較，然后在函數(shù)中迭代兩個二分后的結(jié)果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...
摘要：題目分析一看到問題，而且時間復(fù)雜度要求又是，很自然地就會想到數(shù)組時，如下這道題要求是，所以在上面的基礎(chǔ)上還要進行一些額外操作找到的中點，使用快慢指針法。需要注意的是，找到中點后要把鏈表分成兩段，即兩個鏈表。這部分代碼應(yīng)該近似于這道題的答案。 Sort a linked list in O(n log n) time using constant space complexity. 題...
摘要：注意因為堆中是鏈表節(jié)點，我們在初始化堆時還要新建一個的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個加入堆中 Merge Two Sorted Lists 最新更新請見：https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...
摘要：為減小空間復(fù)雜度，最后結(jié)果直接修改在上，不重新給分配空間。 Easy 021 Merge Two Sorted Lists Description： Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes o...
閱讀 2424·2021-11-25 09:43
閱讀 2944·2021-11-24 09:39
閱讀 3004·2019-08-30 11:10
閱讀 1203·2019-08-29 16:34
閱讀 656·2019-08-29 13:25
閱讀 3410·2019-08-29 11:21
閱讀 2920·2019-08-26 11:39
閱讀 2461·2019-08-26 11:34
