LeetCode（Linked List)21. Merge Two Sorted Lists

迈不过友情╰ 2023-09-24 19:27 62阅读 0赞

LeetCode（Linked List)

# 1.问题 #

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one **sorted list**. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list.*

Example 1:

![b3bed9f14b3c40828c590519970d959e.png][]

> Input: list1 = \[1,2,4\], list2 = \[1,3,4\]  
> Output: \[1,1,2,3,4,4\]

Example 2:

> Input: list1 = \[\], list2 = \[\]  
> Output: \[\]

Example 3:

> Input: list1 = \[\], list2 = \[0\]  
> Output: \[0\]

Constraints:

*  The number of nodes in both lists is in the range \[0, 50\].
 *  \-100 <= Node.val <= 100
 *  Both list1 and list2 are sorted in non-decreasing order.

# 2. 解题思路 #

## 方法1： ##

> 取出list1和list2的值，进行倒序排序，之后新建结点，从结点前面添加数据，之后返回新的结点

## 方法2： ##

> 1.创建新结点，最后的head.next删除创建的结点  
> 2.定义cur做为指针辅助  
> 3.如果list1和list2不为null，list1和list2的值进行比较，cur.next就是最小的值，并移动list1或list2的下一个值  
> 4.如果list1不为null,curr.next=list1  
> 5.如果list2不为null,curr.next=list2  
> 6.返回值为去掉结点head的头节点（0），如果head的头节点为0，无法分配下一个字段next

## 方法3： ##

利用递归

# 3. 代码 #

## 代码1： ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
            ListNode head = null;
            List<Integer> list = new ArrayList<>();//取出list1和list2的值存入list
    
            while (list1 != null) {
        
                list.add(list1.val);
                list1= list1.next;
            }
    
            while (list2 != null) {
        
                list.add(list2.val);
                list2= list2.next;
            }
            Collections.sort(list);//进行升序排序
            Collections.reverse(list);//倒序是为了从后向前添加到ListNode中
            ListNode n = null;
            for(int new_data:list){
        
                n = new ListNode(new_data);
                n.next=head;
                head = n;
            }
            return n;
            
        }
    }

### 本地代码运行 ###

class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d) {
        
                val = d;
                next = null;
            }
        }
    
        public static ListNode mergeTwoLists(ListNode list1, ListNode list2){
        
            ListNode head = null;
            List<Integer> list = new ArrayList<>();
    
            while (list1 != null) {
        
                list.add(list1.val);
                list1= list1.next;
            }
    
            while (list2 != null) {
        
                list.add(list2.val);
                list2= list2.next;
            }
            Collections.sort(list);
            Collections.reverse(list);
            ListNode n = null;
            for(int new_data:list){
        
                n = new ListNode(new_data);
                n.next=head;
                head = n;
            }
            return n;
        }
    
    
        static void printList(ListNode node) {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.next;
            }
        }
    
    
        public static void main(String[] args) {
        
            LinkedList list1 = new LinkedList();
            list1.head = new ListNode(1);
            list1.head.next = new ListNode(3);
            list1.head.next.next = new ListNode(4);
    
            list1.printList(head);
            System.out.println("\n");
    
            LinkedList list2 = new LinkedList();
            list2.head = new ListNode(1);
            list2.head.next = new ListNode(3);
            list2.head.next.next = new ListNode(4);
    
            list2.printList(head);
            System.out.println("\n");
    
            list2.printList( mergeTwoLists(list1.head,list2.head));
        }

### 运行结果 ###

1 3 4 
    
    1 3 4 
    
    1 1 3 3 4 4

## 代码2： ##

1.创建新结点，最后的head.next删除创捷的结点  
2.定义cur做为指针辅助  
3.如果list1和list2不为null，list1和list2的值进行比较，cur.next就是最小的值，并移动list1或list2的下一个值  
4.如果list1不为null,curr.next=list1  
5.如果list2不为null,curr.next=list2  
6.返回值为去掉结点head的头节点（0），如果head的头节点为0，无法分配下一个字段next

public class Solution {
        
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
           ListNode head = new ListNode(0);//1.创建新结点，最后的head.next删除创建的结点
            ListNode cur=head;//2.定义cur做为指针辅助
            while (list1 != null && list2 != null) {
        //3.如果list1和list2不为null，list1和list2的值进行比较，cur.next就是最小的值，并移动list1或list2的下一个值
                if(list1.val<=list2.val){
        
                    cur.next=list1;
                    list1=list1.next;
                }else {
        
                    cur.next=list2;
                    list2 = list2.next;
                }
                cur=cur.next;
            }
            if(list1!=null){
        //4.如果list1不为null,curr.next=list1
                cur.next=list1;
            }
            if(list2!=null){
        //5.如果list2不为null,curr.next=list2
                cur.next=list2;
            }
    
            return head.next;//6.返回值为去掉结点head的头节点（0），如果head的头节点为0，无法分配下一个字段next
        }
    }

> 解题思路基本相同

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(list1 != null && list2 != null) {
        
            if(list1.val <= list2.val) {
        
                cur.next = list1;
                list1 = list1.next;
            } else {
        
                cur.next = l2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        while (list1 != null) {
        
            cur.next = l1;
            list1 = l1.next;
            cur = cur.next;
        }
        while(list2 != null) {
        
            cur.next = list2;
            list2 = list2.next;
            cur = cur.next;
        }
        return head.next;
    }

## 代码3： ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
            ListNode res=null ;
            if(list1==null){
        
                return list2;
            }
    
            if(list2==null){
        
                return list1;
            }
            if(list1.val < list2.val){
        
                res=list1;
                res.next = mergeTwoLists(list1.next,list2) ;
            }
            else{
        
    
                res=list2;
                res.next = mergeTwoLists(list1,list2.next) ;
            }
            return res ;    
        }
    }

[b3bed9f14b3c40828c590519970d959e.png]: https://img-blog.csdnimg.cn/b3bed9f14b3c40828c590519970d959e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Linked List)21. Merge Two Sorted Lists

LeetCode（Linked List) 1.问题 You are given the heads of two sorted linked lists list1

迈不过友情╰/ 2023年09月24日 19:27/ 0 赞/ 63 阅读

相关 LeetCode - Easy - 21. Merge Two Sorted Lists

Topic Linked List Recursion Description [https://leetcode.com/problems/merg

小灰灰/ 2023年01月05日 15:28/ 0 赞/ 119 阅读

相关 [leetcode-排序]--21. Merge Two Sorted Lists

Question 21. Merge Two Sorted Lists > Merge two sorted linked lists and return it as a

待我称王封你为后i/ 2022年07月11日 23:29/ 0 赞/ 119 阅读

相关 [leetcode]: 21. Merge Two Sorted Lists

1.题目 Merge two sorted linked lists and return it as a new list. The new list should b

雨点打透心脏的1/2处/ 2022年06月15日 02:42/ 0 赞/ 124 阅读

相关 Leetcode——21. Merge Two Sorted Lists

1. 概述 1.1 题目 Merge two sorted linked lists and return it as a new list. The new li

布满荆棘的人生/ 2022年06月14日 12:08/ 0 赞/ 131 阅读

相关 leetcode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made b

妖狐艹你老母/ 2022年06月09日 08:00/ 0 赞/ 185 阅读

相关 LeetCode 21.Merge Two Sorted Lists

题目描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4

傷城~/ 2022年05月11日 00:44/ 0 赞/ 117 阅读

相关【leetcode】21. Merge Two Sorted Lists

> Merge two sorted linked lists and return it as a new list. The new list should be made

悠悠/ 2022年01月21日 10:27/ 0 赞/ 186 阅读

相关 Leetcode 21. Merge Two Sorted Lists

[https://leetcode.com/problems/merge-two-sorted-lists/][https_leetcode.com_problems_merg

系统管理员/ 2022年01月10日 23:33/ 0 赞/ 168 阅读

相关 [leetcode-21-Merge Two Sorted Lists]

Merge two sorted linked lists and return it as a new list. The new list should be made

╰+哭是因爲堅強的太久メ/ 2022年01月06日 11:17/ 0 赞/ 147 阅读