草庐IT

【Leetcode刷题】链表的中间结点和合并两个有序链表

是小陳同学呀 2023-06-08 原文

生命如同寓言，其价值不在与长短，而在与内容。                                ——塞涅卡

目录

一.链表的中间结点

1.快慢指针

二.合并两个有序链表 

1.尾插法

一.链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：


输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：
 


输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

做题链接：链表的中间结点

1.快慢指针

我们知道找到链表的尾结点是很容易的，我们只需要遍历整个链表，直到有个结点的next为空，即找到了尾结点。那我们如何找到中间结点呢？这里我们们又要用到双指针了，这里使用的是快慢双指针，快指针一次走两个结点，慢指针一次走一个结点。直到快指针走到尾，即慢指针走到中间结点，我们直接返回慢指针，就是中间结点的位置。
画图理解：
奇数个结点时：

偶数个结点时： 

通过画图，我们就可以很好的理解了，废话不多说，我们直接上代码：

struct ListNode* middleNode(struct ListNode* head){
         struct ListNode*fast=head;
         struct ListNode*slow=head;
         while(fast&&fast->next)
         {
             fast=fast->next->next;
             slow=slow->next;
         }
         return slow;
}

二.合并两个有序链表 

1.尾插法

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

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


示例 2：
输入：l1 = [], l2 = []
输出：[]


示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

做题链接：合并两个有序链表
这题我们可以使用尾插法，我们创建一个哨兵头结点，再一个创建一个头指针，一个尾指针，头指针始终指向最开始的头结点，为了最后的返回。我们依次取下两个链表数值小的那个结点尾接到尾，尾接一个，尾指针往后面走一位。依次类推，把所有的结点尾接起来。
我们还是一样，画图来更好的理解一下。

直接上代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
            if(list1==NULL)
            return list2;
            if(list2==NULL)
            return list1;
           struct ListNode*head=NULL,*tail=NULL;
           head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//创建头结点
            while(list1&&list2)
            {
               if(list1->val>list2->val)
               {
                    tail->next=list2;
                    list2=list2->next;
                }
                else
                {
                    tail->next=list1;
                    list1=list1->next;
                }
                tail=tail->next;
            }
             if(list1)//退出循环，如果list1不为空，即list2尾空。
             tail->next=list1;//只需要把剩下的list1尾接到最后即可
             if(list2)
             tail->next=list2;
             struct ListNode*first=head->next;//保存哨兵位的下一个结点
             free(head);//释放头结点
             head=NULL;
             return first;
}

感谢！！！ 

有序Leetcodexffstrongxff0c链表数据结构学习

有关【Leetcode刷题】链表的中间结点和合并两个有序链表的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  3. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  4. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  5. arrays - 如何在下面的示例中将两个值数组分组为 n 个值数组？ - 2

    我已经有很多两个值数组，例如下面的例子ary=[[1,2],[2,3],[1,3],[4,5],[5,6],[4,7],[7,8],[4,8]]我想把它们分组到[1,2,3],[4,5],[5,6],[4,7,8]因为意思是1和2有关系，2和3有关系，1和3有关系，所以1,2,3都有关系我如何通过ruby​​库或任何算法来做到这一点？ 最佳答案 这是基本Bron–Kerboschalgorithm的Ruby实现:classGraphdefinitialize(edges)@edges=edgesenddeffind_maximum_

  6. ruby - 尝试比较两个文本文件，并根据信息创建第三个 - 2

    我有两个文本文件，master.txt和926.txt。如果926.txt中有一行不在master.txt中，我想写入一个新文件notinbook.txt。我写了我能想到的最好的东西，但考虑到我是一个糟糕的/新手程序员，它失败了。这是我的东西g=File.new("notinbook.txt","w")File.open("926.txt","r")do|f|while(line=f.gets)x=line.chompifFile.open("master.txt","w")do|h|endwhile(line=h.gets)ifline.chomp!=xputslineendende

  7. ruby - 在两个 ActiveRecord 类之间合并/复制属性的好方法？ - 2

    之前有人问过这个问题，我发现了以下clip关于如何一次设置一个类对象的所有属性，但由于批量分配保护，这在Rails中是不可能的。(例如，您不能Object.attributes={})有没有一种很好的方法可以将一个类的属性合并到另一个类中？object1.attributes=object2.attributes.inject({}){|h,(k,v)|h[k]=vifObjectModel.column_names.include?(k);h}谢谢。 最佳答案 利用assign_attributes使用:without_prote

  8. ruby-on-rails - ruby 中两个哈希之间的变化 - 2

    我有两个具有以下格式的哈希mydetails[x['Id']]=x['Amount']这将包含如下数据hash1={"A"=>"0","B"=>"1","C"=>"0","F"=>"1"}hash2={"A"=>"0","B"=>"3","C"=>"0","E"=>"1"}我期待这样的输出:Differencesinhash:"B,F,E"非常感谢任何帮助。 最佳答案 这个解决方案可能更容易理解:(hash1.keys|hash2.keys).select{|key|hash1[key]!=hash2[key]}Array#|返回2

  9. ruby - 检查 ruby 中的两个范围是否重叠 - 2

    我知道我能做到:(1..30).cover?(2)=>true但是当我尝试对另一个范围执行相同操作时，它总是返回false:(1..30).cover?(2..3)=>false所以我的问题是-是否有任何优雅的方法来比较ruby​​中的两个范围？在我的例子中，我想检查两个日期时间范围是否重叠。提前致谢。 最佳答案 给定范围A的两个范围重叠，当:范围B从范围A开始，范围B在范围A内结束或范围B在范围A之前开始，在范围A之后结束例子:RangeA|-----||-----|Case1|-----|Case2|-|Case1+2|----

  10. ruby-on-rails - Ruby:如何在 Ruby 中读取包含两个 header 的 CSV 文件？ - 2

    我有一个“.CSV”文件，我正尝试在ruby​​中使用CSV对其进行解析。该文件虽然有两行标题，但我以前从未遇到过这种情况，也不知道如何处理。以下是标题和行的示例。第1行"InstitutionID","Institution","GameDate","UniformNumber","LastName","FirstName","Rushing","","","","","Passing","","","","","","TotalOff.","","Receiving","","","PassInt","","","FumbleRet","","","Punting","","Pun

随机推荐