合并两个有序链表

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

实现

使用归并排序的思路

归并排序中有个思路是将两个已排好序的数组合并到一个数组中。这题刚好可以用归并排序的思路来解决。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l1Node = l1;
        ListNode l2Node = l2;
        ListNode head = new ListNode(0);
        // 新链表当前节点
        ListNode cur = cur = head;
         // 当跳出循环的时候肯定有个链表为空。说明为空的链表所有数据已        
         //放到新链表中
        while(l1Node != null && l2Node != null) {
            if(l1Node.val < l2Node.val) {
                ListNode node = new ListNode(l1Node.val);
                cur.next = node;
                cur = node;
                l1Node = l1Node.next;
            }else {
                ListNode node = new ListNode(l2Node.val);
                cur.next = node;
                cur = node;
                l2Node = l2Node.next;
            }
        }
        //当l1链表不为空直接将剩余的数据链接到新链表中。
        if(l1Node != null) {
            cur.next = l1Node;
        }
        ////当l2链表不为空直接将剩余的数据链接到新链表中。
        if(l2Node != null) {
            cur.next = l2Node;
        }
        return head.next;
    }
}

根据排序后的val新建链表

思路就是将循环遍历两个链表，将val值放入List，然后将List中的数字排序，接着根据排序后的List新建链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l1Node = l1;
        List<Integer> list = new ArrayList();
       // 遍历l1Node链表
        while(l1Node != null) {
            list.add(l1Node.val);
            l1Node = l1Node.next;
        }
       //遍历l2Node链表
        ListNode l2Node = l2;
        while(l2Node != null) {
            list.add(l2Node.val);
            l2Node = l2Node.next;
        }
        //排序
        Collections.sort(list);
        // 新建链表
        ListNode head = new ListNode(0);
        ListNode node = head;
        for(int i=0;i<list.size();i++) {
                ListNode next =new ListNode(list.get(i));
                node.next = next;
                node = next;
        }
        return head.next;
        
    }
}