剑指offer:合并两个排序的链表（Java）

darkbaby123 发布于2019-08-16 18:39 / 585人阅读

摘要：问题描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1.问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

2.思路

方法1:非递归方法

根据题目这个很类似排序中的外排过程,两个数组分别排好序,然后再把他们整体进行排序.所以这道题思想很简单,就是用两个变量分别遍历两个链表.比较遍历到的两个节点的值,小的节点就断开与后面的连接,连到遍历到的另一个节点上,同时让小的节点向后移动一位,大节点位置不变,所以这里需要一个变量来记录值较小的节点后面一个节点,保证断开与后面的连接后可以获得后面的节点.这样执行循环操作,直到一个链表循环到最后停止.就会把两个链表合成一个有序的新链表.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)    //判断链表1是否为null,如果为null,直接返回链表2.
            return list2;
        else if(list2 == null)    //判断链表2是否为null.
            return list1; 
        ListNode pNode1 = list1;    //记录链表1的头节点,因为要返回新的链表,所以最后比较一下返回值较小的头节点
        ListNode pNode2 = list2;    //记录链表2的头节点  
        ListNode next = null;    //小节点断开与后面的连接时用于记录小节点后面的一个节点,保证能遍历到。
        while(list1 != null && list2 != null){    //只要有一个链表到最后就停止循环
            if(list1.val <= list2.val){    //较小的节点连到大节点上
                next = list1.next;
                list1.next = list2;
                list1 = next;
            } else{
                next = list2.next;
                list2.next = list1;
                list2 = next;
            }
        }
        return pNode1.val <= pNode2.val ? pNode1 : pNode2;    //返回两个头节点中较小的那个.
    }
}

方法2:递归方法

关键就是判断list1和list2的val值的大小,然后改变list1或list2的next的指向.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next,list2);    
            //这里是改变list1的next的指向,里面填list1.next是为了让list1的节点向后移动一位.
            return list1;
        }else{
            list2.next = Merge(list2.next,list1);
            return list2;
        }
    }
}

递归方法参考牛客网:披萨大叔的方法

私有云服务器托管链表排序合并链表的c语言链表排序算法合并排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75505.html

PHPer也刷《剑指Offer》之链表

摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。温故知新链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。根据类型可以分为单链表、双链表、环形链表、...

daydream 2019-07-01 10:11 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
《剑指offer》分解让复杂问题更简单

摘要：拆分链表，将和进行拆分，保证原始链表不受影响。要求不能创建任何新的结点，只能调整树中结点指针的指向。输入一个字符串长度不超过可能有字符重复字符只包括大小写字母。递归，记录一个当前节点的位置，该位置指向最后一个节点时记录一次排列。 1.复杂链表的复制输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的hea...

wawor4827 2019-08-23 15:27 评论0 收藏0