当前位置： 移动技术网 > 移动技术>移动开发>IOS > 剑指offer 25. 合并两个排序的有序链表

剑指offer 25. 合并两个排序的有序链表

2020年07月13日  | 移动技术网移动技术  | 我要评论

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

限制：

0 <= 链表长度 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

首先这是两个排序链表，要合成为一个有序链表，我们大体思路就是先定义出新的链表的头（newHead），然后再将这两个排序链表的每一个节点的值大小比较，按照顺序一一串起来就好了。

/**
 * 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 newHead = new ListNode(-1);//定义出新的头节点
        ListNode tmp = newHead; 
        //tmp的永远指向的是当前新串起来的链表的尾节点，为串下一个节点做准备
      
        while(l1!=null && l2!=null) { //首先保证在l1 l2都不空的情况下
            if(l1.val < l2.val) {  //如果l1节点的值 小于 l2节点的值
                tmp.next = l1;  //tmp.next 指向l1 当前指向的节点串在
                l1 = l1.next;	//l1向自己的下一个节点走
                tmp = tmp.next; //tmp向自己的下一个节点走
            }else {
                tmp.next = l2;
                l2 = l2.next;
                tmp = tmp.next;
            }
        }
        
        //当跳出 while循环，我们要考虑跳出循环的条件：
        //1. l1 l2都刚好遍历完，每一个节点都已经放到了新的有序链表中
        //2. l1或者l2两个长度不等，其中有一个遍历到头了
        
        if(l1 != null) {	//对l1 没遍历完情况做出处理
            tmp.next  = l1;	//将l1剩余节点放到新的有序链表后即可
        }
        if(l2 != null) {	//对l2 没遍历完情况做出处理
            tmp.next = l2;
        }

        return newHead.next; //返回newHead.next,因为newHead是我们定义
        //的一个标志头节点的（val==-1），新的有序链表跟在它后面，也就是说新的
        //头节点的地址在newHead.next域中。

    }
}

本文地址：https://blog.csdn.net/wqq3670/article/details/107293682

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网