C/C++教程

[Leetcode]21. 合并两个有序链表

本文主要是介绍[Leetcode]21. 合并两个有序链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com)

思路:

有两个有序链表l1和l2,这里的l1和l2是分别指向这两个有序链表的,按着顺序迭代两个链表。

 

无虚拟节点的情况:

确定合并链表的头节点指针head这里要对两个链表的情况进行划分,有四种情况:

1. 若l1==null && l2 == null,则合并的链表自然为空,head=null

2. 若l1 == null && l2 != null,则合并的链表即为l2,返回l2即可,head=l2

3. 若l1 != null && l2 == null,则合并的链表即为l1,返回l1即可,head=l1

4.若l1 != null && l2!=null,则比较l1和l2指向的元素大小,若l1小于于等于l2,则p=l1,指针l1向后移动一个位置,否则p=l2,指针l2向后移动一个位置。

 

对于第4中情况:

将head赋值给一个新的节点p用于合拼操作的情况

4.1 迭代:当当前的l1和l2都不为null的时候,比较大小,若l1小于于等于l2,则p = l1,l1 = l1.next,p = p.next;否则p = l2,l2 = l2.next,p=p.next;

4.2 当上面的迭代循环完成时,如l1==null,说明链表l1指向的链表已经全部合并,此时应该让指针p指向l2指向的剩余第二个链表的部分:p.next = l2;同理也有p.next = l1;

算法最后返回头节点head即可

代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       ListNode head = list1;
       //若l1==null && l2 == null,则合并的链表自然为空
       if(list1 == null && list2 == null){
           return head;
       }
       // 若l1 == null && l2 != null,则合并的链表即为l2,返回l2即可
       if(list1 == null && list2 != null){
           return list2;
       }
       // 若l1 != null && l2 == null,则合并的链表即为l1,返回l1即可
       if(list1 != null && list2 == null){
           return head;
       }
       
       // 上面的情况都没有满足的情况自然是l1 != null && l2!=null,则比较l1和l2指向的元素大小
       // 确定头节点
       if(list1.val<= list2.val){
           head = list1;
           // 指针往后一步
           list1 = list1.next;
       }else {
           head = list2;
           // 指针前进一步
           list2 = list2.next;
       }

        ListNode p = head;

       //从头节点指针p开始操作
       while(list1!= null && list2!= null){
           if(list1.val<= list2.val){
               // 如果要在这里确定头节点,p = list1,操作是不统一的,需要分开判断
               p.next = list1;
               list1 = list1.next;
           }else {
               p.next = list2;
               list2 = list2.next;
           }
           p = p.next;
       }

       if(list1 == null){
           p.next = list2;
       }

       if(list2 == null){
           p.next = list1;
       }

       return head;

    }
}

从上面的代码,我们也可以看出有很多判断链表是否为空链表的操作,判断空指针的操作,此时如果我们使用虚拟头节点的时候,

就不需要这么多的判断的操作了也不需要再对头节点单独进行操作,

操作是不统一的,需要分开判断

此外,在对两个链表的操作的过程中,balalala的,不应该在头节点指针list1和list2上操作,应该重新创建新指针指向两个链表再进行操作:

加上虚拟节点

改进的代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟节点
        ListNode dumpy = new ListNode(-1);
        ListNode p = dumpy;
        ListNode p1 = list1,p2 = list2;
       //从头节点指针p开始操作
       while(p1!= null && p2!= null){
           if(p1.val<= p2.val){
               p.next = p1;
               p1 = p1.next;
           }else {
               p.next = p2;
               p2 = p2.next;
           }
           p = p.next;
       }

       if(p1 == null){
           p.next = p2;
       }

       if(p2 == null){
           p.next = p1;
       }
       return dumpy.next;

    }
}

  

 

这篇关于[Leetcode]21. 合并两个有序链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!