欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-07 20:20:07
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。示例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著作权归领扣网络所有。商业转载请联系官方授权,非...

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

示例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