題目描述

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回型宙。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

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

實(shí)現(xiàn)

使用歸并排序的思路

歸并排序中有個(gè)思路是將兩個(gè)已排好序的數(shù)組合并到一個(gè)數(shù)組中进泼。這題剛好可以用歸并排序的思路來(lái)解決苫耸。

/**
 * 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);
        // 新鏈表當(dāng)前節(jié)點(diǎn)
        ListNode cur = cur = head;
         // 當(dāng)跳出循環(huán)的時(shí)候肯定有個(gè)鏈表為空蜈块。說(shuō)明為空的鏈表所有數(shù)據(jù)已        
         //放到新鏈表中
        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;
            }
        }
        //當(dāng)l1鏈表不為空直接將剩余的數(shù)據(jù)鏈接到新鏈表中曾沈。
        if(l1Node != null) {
            cur.next = l1Node;
        }
        ////當(dāng)l2鏈表不為空直接將剩余的數(shù)據(jù)鏈接到新鏈表中。
        if(l2Node != null) {
            cur.next = l2Node;
        }
        return head.next;
    }
}

根據(jù)排序后的val新建鏈表

思路就是將循環(huán)遍歷兩個(gè)鏈表烙博，將val值放入List瑟蜈，然后將List中的數(shù)字排序，接著根據(jù)排序后的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;
        
    }
}