题目链接: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; } }