剑指Offer——合并两个排序的链表

约定不等于承诺〃 2021-12-03 21:17 233阅读 0赞

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