• 21.合并两个有序链表
  • 题目
  • 题解-递归
  • 题解-迭代
  • 链表
    • 链表的基本操作

21.合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解-递归

链表问题最需要考虑的是不要断链

递归的三部曲

递归返回值和参数
我们需要把两个链表合并成一个链表，那么参数应该是两个链表的头节点。递归返回排好序的头节点。

public ListNode mergeTwoLists(ListNode list1, ListNode list2)

递归什么时候结束

当其中一个链表为空的时候就可以结束了,直接返回另外一个链表的头节点就行了

if(list1==null)return list2;
if(list2==null)return list1;

本层递归逻辑

本层的两个链表要排好序，本层比较头节点的大小，小的节点做开头。这样处理之后，肯定可以后续的递归中，这个节点就是最小的，就是头节点。
大的和小的后面的链表继续进行排序。

if(list1.val<=list2.val) {
	//list1值更小，list1做头节点。可以确定下来的。剩下的和list2继续排序。
	list1.next = 	mergeTwoLists(list1.next,list2);  //mergeTwoLists表示已经排好序了
	return list1; //把本层处理好的头节点返回
}
else{
	list2.next = mergeTwoLists(list1,list2.next);
	return list2;
}

代码

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null)return list2;
        else if(list2==null)return list1;
        else {
           if(list1.val<=list2.val) {
	            list1.next = 	mergeTwoLists(list1.next,list2);
            	return list1; 
            }
        else{
	            list2.next = mergeTwoLists(list1,list2.next);
	            return list2;
        }
        }
}
}

题解-迭代

合并的问题可以新建一个收集结果的容器

合并的问题都可以尝试新建一个链表res

比较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 result = new ListNode(0); //新建一个节点，0可以是任何值，返回的是result.next，这里新建一个节点是因为下面要使用result.next
        ListNode tmp = result;
        while(list1!=null && list2!=null){
            //小的先出来
            if(list1.val<=list2.val){
                tmp.next = list1;
                list1 = list1.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
            }
            tmp = tmp.next;
        }
        //把剩下的链接起来
        if(list1==null) tmp.next=list2;
        if(list2==null) tmp.next=list1;
        return result.next;
        
}
}

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

链表适合在数据需要有一定顺序，但是又需要进行频繁增删除的场景。

头结点：在单链表的第一个结点(有效元素)之前附设的一个结点，称之为头结点。
头指针：指向头结点的指针称为头指针。
首节点(首元结点)：首节点就是第一个元素(头元素)的结点

虚拟节点
定义：数据结构中，在链表的第一个结点之前附设一个结点，它没有直接前驱，称之为虚拟结点。虚拟结点的数据域可以不存储任何信息，虚拟结点的指针域存储指向第一个结点的指针。

作用：对链表进行增删时统一算法逻辑，减少边界处理（避免了判断是否是空表或者是增删的节点是否为第一个节点）

尾节点
定义：数据结构中，尾结点是指链表中最后一个节点，即存储最后一个元素的节点。

作用：由于移动到链表末尾需要线性的时间，因此在链表末尾插入元素会很耗时， 增加尾节点便于在链表末尾以 O(1) 的时间插入元素。

链表的基本操作

插入
插入只需要考虑要插入位置前驱节点和后继节点（双向链表的情况下需要更新后继节点）即可，其他节点不受影响，因此在给定指针的情况下插入的操作时间复杂度为O(1)。这里给定指针中的指针指的是插入位置的前驱节点。

伪代码：

temp = 待插入位置的前驱节点.next
待插入位置的前驱节点.next = 待插入指针
待插入指针.next = temp

如果没有给定指针，我们需要先遍历找到节点，因此最坏情况下时间复杂度为 O(N)。

删除
只需要将需要删除的节点的前驱指针的 next 指针修正为其下下个节点即可，注意考虑边界条件。

伪代码：

待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next

遍历
遍历比较简单，直接上伪代码。

伪代码：

当前指针 =  头指针
while 当前指针不为空 {
   print(当前节点)
   当前指针 = 当前指针.next
}