題目來自于leetcode，要求是將兩個已經有序的鏈表拼接成一個有序的鏈表，鏈表結構如下：

public class ListNode{int val;ListNode next;ListNode(int x){val=x;}}

示意圖如下，一個長方形成為節點，一個鏈表至少有一個節點。

方法一：首先創建一個新的鏈表L，比較了L1和L2當前結點的Val，小的加入到L中，同時將節點向后移，

　　　　直到有一個鏈表為空。最后將另一個非空的鏈表添加到L即可。時間復雜度為O(n+m).

　　　　Header:新鏈表的頭節點，pre作為當前鏈表的最后一個節點，具體步驟如下：

　　　　1.判斷L1和L2其中一個是否為空，若有為空，執行3，否則執行2

　　　　2.比較L1和L2的Val值，小的添加到pre節點的后面，并向右移動一個節點（ListNode=ListNode.next，注意此時鏈表ListNode已經發生改變了）,

　　　　同時pre指向Header鏈表的最后一個。執行1.

　　　　3.若L1不為空，則將L1添加到pre的后面。若L2不為空則將L2添加到pre節點的后面。

　　　　具體實現代碼如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode header=new ListNode(0);ListNode pre=header;while(l1!=null&&l2!=null){if(l1.val>l2.val){pre.next=l2;l2=l2.next;}else{pre.next=l1;l1=l1.next;}pre=pre.next;}if(l2!=null){pre.next=l2;}if(l1!=null){pre.next=l1;}return header.next;}

方法二：由于L1和L2已經是有序了，所以可以考慮將L2插入到L1中，這里只講插入操作怎么進行，具體過程看java代碼

　　　　

　　　　Header 任然為頭結點，pre為當前節點的末節點，，紅線代表需要修改的指向，綠線代表需要刪除的指向

，現在考慮L2的Val比L1小的情況，

　　　　插入步驟如下：

　　　　1。保留L2下一個節點為next

　　　　2.修改L2下一個節點的指向為pre指向的下個節點

　　　　3.修改pre指向的節點為L2

　　　　4.將pre和L2各自向右移動一個節點

　　　　具體代碼如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode helper=new ListNode(0);ListNode pre=helper;helper.next=l1;while(l1!=null&&l2!=null){if(l1.val>l2.val){ListNode next=l2.next;l2.next=pre.next;pre.next=l2;l2=next;}else{l1=l1.next;}pre=pre.next;}if(l2!=null){pre.next=l2;}return helper.next;}

　方法3：采用遞歸的思想，若將函數看成求兩個鏈表當前較小的節點，遞歸結束為兩個鏈表中有一個為null。

　　　　步驟一：1.創建一個節點header為L1和L2較小的節點

　　　　　　　　2.創建一個中間變量nonheader為L1和L2較大的節點

·　　　　　　　? 3.將header下個節點指向遞歸函數的返回結果，但此時傳參中header已經向右移動了一個單位

　　　

　　代碼如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1==null) return l1;if(l2==null) return l2;ListNode head=(l1.val<l2.val)?l1:l2;ListNode nonhead=(l1.val<l2.val)?l2:l1;head.next=mergeTwoLists(head.next,nonhead);return head;}

這三種方法都可以實現，總體效果最好的時遞歸的方法。如有紕漏，希望能得到大家的幫助。

轉載于:https://www.cnblogs.com/bufferflies/p/7644347.html

總結

以上是生活随笔為你收集整理的21. Merge Two Sorted Lists的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。