帮大家巩固一下链表知识我把两道题的链接放到下面大家可以去做一下。

题目链接

励志语句生活也许会让我们遍体鳞伤但最终这些伤口会成为我们一辈子的财富。

目录1、合并两个排序链表1.1

输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围

\le

O(n)O(n)如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示

1.2

申请一个虚拟的头结点cur指向这个虚拟头结点while循环进行进行遍历只要其中一个链表为空结束循环循环里面进行判断list1和list2谁较小就与cur进行拼接结束循环后说明至少有一个链表为空因此cur拼接不为空的链表也可能两个都为空至少拼接一个因为链表要以null结束。

1.4

ListNode(-1);//cur指向当前的虚拟节点ListNode

cur

newHead;//while循环,只要遍历完其中一个链表就结束循环while(list1

null

}}//拼接不为空的两个都遍历完的时候任意拼接一个if(list1

null){cur.next

聪明的大家或许已经发现这道题是刚刚那道题的升级版牛客网标注着难题的标志其实也没那么难找到了规律掌握了思想做起来很容易。

2.1

个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围节点总数

\le

首先大家肯定会想到粗鲁的办法从前往后依次遍历比较然后进行拼接这样不仅时间复杂度高而且比较麻烦搞的头晕目眩也不一定能得出正确的答案。

那么我们需要想到另一种方法分治思想这种思想我们在快排和归并排序中见过既然接触过我们肯定有点基础我们来回忆一下所谓的分治思想。

分治就是分而治之可以这样理解解决一个大问题的时候首先把大问题化解成若干个小问题小问题与大问题的性质保持一致逐个解决完小问题然后合并最终就解决了所谓的大问题。

总结分治思想

大问题化解为若干个子问题。

计算各个子问题。

合并所有子问题的解。

看到这里大家应该对分治思想有了一定的认识那么接下来我们分析一下这道题。

大问题化解成小问题需要写一个小问题的递归方法因此我们构造了func(ArrayList

lists,int

right)方法。

分治思想需要注意边界这里的左边界和右边界是以链表为单位的而不是节点。

我们还需要一个合并两个有序链表的方法在上面那道题就是我们可以直接复制过来。

2.4

{//需要返回一个节点//传参func参数为集合lists左边界0和右边界lists.size()-1return

func(lists,0,lists.size()-1);}//下面是一个递归方法//也就是大问题化解为小问题的过程private

ListNode

right){//左边界大于右边界的时候化解结束if(left

right){return

null;//左边界等于右边界的时候返回该节点//因为这里左右节点的下标相同//所以写lists.get(left)或者lists.get(right)都行}

else

right的时候就要再次进行划分//因为咱们只有合并两个链表的方法}

else{int

merge(func(lists,left,mid),func(lists,mid1,right));}}//下面的方法就是第一道题的答案就不做详细说明了private

ListNode

我相信大家通过这两道题学到了很多第一道题比较简单但大家不要眼高手低还是多加练习熟能生巧第二道题需要掌握分治思想可能大家一看到递归就会头疼代码不多但是却不容易理解这个东西需要多加练习琢磨画图需要自己不断去品味去感受不要畏惧做的多了你会感到所谓的递归其实没有那么难。

哈哈今天的内容到这里也就结束了希望小小的我能够帮助到大家。