1、題目描述

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

2、代碼實現

1 package com.baozi.offer; 2 3 /** 4 * @author BaoZi 5 * @create 2019-07-11-16:14 6 */ 7 public class Offer13 { 8 public static void main(String[] args) { 9 ListNode n1 = new ListNode(1); 10 ListNode n2 = new ListNode(2); 11 ListNode n3 = new ListNode(4); 12 ListNode n4 = new ListNode(6); 13 ListNode n5 = new ListNode(8); 14 ListNode n6 = new ListNode(10); 15 n1.next = n2; 16 n2.next = n3; 17 n3.next = n4; 18 n4.next = n5; 19 n5.next = n6; 20 n6.next = null; 21 22 ListNode l1 = new ListNode(1); 23 ListNode l2 = new ListNode(3); 24 ListNode l3 = new ListNode(5); 25 ListNode l4 = new ListNode(7); 26 ListNode l5 = new ListNode(9); 27 ListNode l6 = new ListNode(11); 28 l1.next = l2; 29 l2.next = l3; 30 l3.next = l4; 31 l4.next = l5; 32 l5.next = l6; 33 l6.next = null; 34 Offer13 offer13 = new Offer13(); 35 ListNode merge = offer13.Merge(l1, n1); 36 ListNode temp = merge; 37 while (temp != null) { 38 System.out.print(temp.val + " "); 39 temp = temp.next; 40 } 41 } 42 43 public ListNode Merge(ListNode list1, ListNode list2) { 44 //首先進行特殊情況的判斷，并且只有當兩個鏈表都為空的時候才會返回null 45 if (list1 == null && list2 == null) { 46 return null; 47 } 48 //創建一個新的鏈表頭節點，該鏈表中存放的元素就是兩個給定鏈表合并之后的元素 49 ListNode head = new ListNode(-1); 50 ListNode head_temp = head; 51 //定義兩個指針分別指向兩個給定的鏈表list1和list2 52 ListNode temp1 = list1; 53 ListNode temp2 = list2; 54 //當兩個臨時指針都不為空的時候 55 while (temp1 != null && temp2 != null) { 56 //這里使用的是尾插法創建鏈表 57 if (temp1.val <= temp2.val) { 58 ListNode temp = temp1.next; 59 head_temp.next = temp1; 60 head_temp = head_temp.next; 61 temp1 = temp; 62 } else { 63 ListNode temp = temp2.next; 64 head_temp.next = temp2; 65 head_temp = head_temp.next; 66 temp2 = temp; 67 } 68 } 69 //這種情況是當list2已經遍歷完了但是list1還沒有遍歷完，這時候還需要把list1剩余部分全部添加到新鏈表的后面 70 if (temp1 != null) { 71 head_temp.next = temp1; 72 } 73 //這種情況是當list1已經遍歷完了但是list2還沒有遍歷完，這時候還需要把list2剩余部分全部添加到新鏈表的后面 74 if (temp2 != null) { 75 head_temp.next = temp2; 76 } 77 //因為創建的頭節點只是為了方便操作，所以在最后輸出返回值的時候需要去掉 78 return head.next; 79 } 80 }

?

轉載于:https://www.cnblogs.com/BaoZiY/p/11170899.html

總結

以上是生活随笔為你收集整理的剑指Offer——合并两个排序的链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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