LC-21:合并两个有序链表

LC-21:合并两个有序链表

                                        

                    

我的算法思路实现一

public class AtomicDemone {
    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;

        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(3);
        ListNode node7 = new ListNode(4);
        node5.next = node6;
        node6.next = node7;

        ListNode listNode = mergeTwoLists(node1, node5);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ArrayList<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);

        ListNode result = new ListNode(-1);
        ListNode current = result;

        for (int i = 0; i < list.size(); i++) {
            current.next = new ListNode(list.get(i));
            current = current.next;
        }
        return result.next;
    }
}

这个算法的思路就是抓住了,这个题的一个点,就是可以实现自定义链表,可以使用构造函数创建节点,创建链表。
主要思路:使用ArrayList对两个链表进行遍历。记录里面的所有的元素,然后使用JDK的集合工具类Collections.sort(list)进行排序,然后对list集合中的所有的元素进行遍历,实现对每一个结点创建构建链表,然后然后链表。

我的算法思路实现二

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode result = new ListNode(-1);
        ListNode current = result;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) { // 对于list1中的值小于等于list2 ,那就是存list1中的值
                current.next = new ListNode(list1.val); // 存在新的链表中
                current = current.next;
                list1 = list1.next;
            } else {  // 对于list1中的值大于list2 ,那就是存list2中的值
                current.next = new ListNode(list2.val); // 存在新的链表中
                current = current.next;
                list2 = list2.next;
            }
        }

        // 对list1进行判空
        if (list1 != null) {
            current.next = list1;
        }

        // 对list2进行判空
        if (list2 != null) {
            current.next = list2;
        }
        
        return result.next;
    }

这个算法的代码依旧是可以通过的,与第一个思想实现是不同的。现在这个是直接对两个链表进行直接判断,不需要数组进行存储,对链表中的每一个结点进行判断,对于list1的值小于list2的值的话,list1妨碍新的链表中,list1向后走一位,list2不动,所以我使用if语句实现。
            if (list1.val <= list2.val) { // 对于list1中的值小于等于list2 ,那就是存list1中的值
                current.next = new ListNode(list1.val); // 存在新的链表中
                current = current.next;
                list1 = list1.next;
            } else {  // 对于list1中的值大于list2 ,那就是存list2中的值
                current.next = new ListNode(list2.val); // 存在新的链表中
                current = current.next;
                list2 = list2.next;
            }
会发现,在if-else中对于链表的后移都是不同的,谁的值存放了就往后移动,这样的话,能够确保就算不是同一个上下位置的话,我也能够保持数据的比较。
最后,我要对list1和list2要进行判断是否有多余的元素,因为这个链表是一个有序的,所以,若是有多余的,就直接连接,反正list1或list2的指针是一直往后移动的。
        // 对list1进行判空
        if (list1 != null) {
            current.next = list1;
        }

        // 对list2进行判空
        if (list2 != null) {
            current.next = list2;
        }

全部评论

相关推荐

11-09 17:30
门头沟学院 Java
TYUT太摆金星:我也是,好几个华为的社招找我了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务