题目描述

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

答案

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode result = new ListNode(-1);
        ListNode res = result;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
               res.next = cur1;
                cur1 = cur1.next;
            }else{
               res.next = cur2;
                cur2 = cur2.next;
            }
            res = res.next;
        }
        if(cur1 != null){
            res.next = cur1;
        }
        if(cur2 != null){
            res.next = cur2;
        }
        return result.next;
    }
}

解析

  1. 如果l1指向的结点值小于等于l2指向的结点值,则将l1指向的结点值链接到cur的next指针,然后l1指向下一个结点值
  2. 否则,让l2指向下一个结点值
  3. 循环步骤1,2,直到l1或者l2为nullptr
  4. 将l1或者l2剩下的部分链接到cur的后面

首先,这题的其中一个思想就是一旦其中一个链表结束了,另一个链表应该直接拼上去,一开始while循环我想的是让两个链表同时为空的时候结束循环,然后在循环体内部直接拼接。

后来发现这种想法比较蠢,我只需要让其中一个为空的时候直接跳出循环,把剩余的拼上就好了。

另外就是要注意下拼接时的顺序,我一直想的是先让容器接链表下一个值再新建next节点,脑子没拧过劲来,其实只需要给next结点赋值,然后让本体跟上就可以了


醉后不知天在水,满船清梦压星河