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:

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 ;    
    }
}