`
小羊fc
  • 浏览: 90276 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

合并两个有序链表

    博客分类:
  • C++
 
阅读更多

面试中遇到了道题!合并两个有序链表

贴贴代码!

#include <iostream>

using namespace std;
struct linkNode
{
    int element;
    linkNode *next;
};

linkNode * getLink(linkNode *firstLink,linkNode *secondLink)
{
    if(firstLink->element <= secondLink->element) {
         linkNode * head = firstLink;
         while(firstLink->element <= secondLink->element)
         {
             if(firstLink->next != NULL)
             {
                  if(firstLink->next->element > secondLink->element)
                  {
                     linkNode * tmp = firstLink->next;
                     firstLink->next = secondLink;
                     secondLink = secondLink->next;
                     firstLink->next->next = tmp;
                     if(secondLink == NULL) {
                         break;
                     }
                  }
                  firstLink = firstLink->next;
             }
             else
             {
                  firstLink->next = secondLink;
                  break;
             }

         }
         return head;
    }else {
        return getLink(secondLink,firstLink);
    }
}

void print(linkNode * node)//用于打印链表
{
    while(node->next != NULL)
    {
        cout << node->element << " ";
        node = node->next;
    }
    cout << node->element << "";
}

linkNode * buildLink(int array[],int size)
{
    linkNode * link = new linkNode();
    link->element = array[0];
    linkNode * tmplink = link;
    for(int i = 1 ; i < size ; i ++)
    {
        linkNode * tmp = new linkNode();
        tmp->element = array[i];
        tmplink->next = tmp;
        tmplink = tmplink->next;
    }
    return link;
}

int main()
{
    //初始化链表(有序)
    int a [] = {1,4,5,10,10};
    int b [] = {1,2,5,7};

    linkNode * firstLink = buildLink(a,5);

    linkNode * secondLink = buildLink(b,4);

    //显示

    print(firstLink);
    cout << endl;
    print(secondLink);
    //合并
    cout << endl;
    linkNode *newLink = getLink(firstLink,secondLink);
    print(newLink);
    cout << endl;
    return 0;
}
 

 



  


  
0
3
分享到:
评论
5 楼 小羊fc 2012-10-11  
liuInsect 写道
小羊fc 写道
liuInsect 写道
“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊? 如果第一个链表的元素都大于第二个链表,
就直接返回第一个链表?

这个情况确实没想好!我改改!




思路是, 一定要把第一个链表遍历完 在遍历的时候与第二个链表比 来确定谁放在但当前位置。
直到第一个链表结束 若第二个链表还有元素 全部copy就行。

我按的似乎是这个思路呀!
4 楼 小羊fc 2012-10-11  
liuInsect 写道
“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊? 如果第一个链表的元素都大于第二个链表,
就直接返回第一个链表?

改好了,谢谢你帮我指出错误,那种情况应该可以解决了!
3 楼 liuInsect 2012-10-11  
小羊fc 写道
liuInsect 写道
“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊? 如果第一个链表的元素都大于第二个链表,
就直接返回第一个链表?

这个情况确实没想好!我改改!




思路是, 一定要把第一个链表遍历完 在遍历的时候与第二个链表比 来确定谁放在但当前位置。
直到第一个链表结束 若第二个链表还有元素 全部copy就行。
2 楼 小羊fc 2012-10-11  
liuInsect 写道
“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊? 如果第一个链表的元素都大于第二个链表,
就直接返回第一个链表?

这个情况确实没想好!我改改!
1 楼 liuInsect 2012-10-11  
“   while(firstLink->element <= secondtLink->element)  ”

这个是啥意思啊? 如果第一个链表的元素都大于第二个链表,
就直接返回第一个链表?

相关推荐

    合并两个有序链表.zip

    两个有序链表的合并pta本文详细介绍了合并两个有序链表的算法原理、实现步骤、代码示例以及性能分析。通过掌握这一算法,我们可以更加高效地处理有序链表数据,提高程序的性能和可靠性。未来,随着数据规模的扩大和...

    PTA 两个有序链表序列的合并

    总结来说,"PTA 两个有序链表序列的合并"这个题目要求我们掌握链表的基本操作,理解链表的特性,以及如何有效地合并两个有序链表。通过解决这个问题,我们可以加深对链表数据结构的理解,同时锻炼我们的逻辑思维和...

    合并两个有序链表.pptx

    首先,我们可以看到PPT中的"合并两个有序链表"是通过创建一个虚拟头结点来实现的。虚拟头结点是一个不包含任何实际数据的特殊节点,它的主要作用是方便处理链表的合并过程。在这个例子中,`Assumehead`就是这个虚拟...

    php-leetcode题解之合并两个有序链表.zip

    在本压缩包“php-leetcode题解之合并两个有序链表.zip”中,主要涉及到的是一个编程问题,即如何用PHP解决LeetCode上的经典问题——“合并两个有序链表”。LeetCode是一个广受欢迎的在线平台,它提供了各种算法题目...

    合并K个升序链表(以合并两个有序链表为基础)1

    这个问题可以通过递归或迭代的方法来解决,这里我们将重点讨论基于合并两个有序链表的解决方案。 首先,我们需要了解链表的基本结构。在 C++ 中,链表节点通常定义为一个结构体或类,包含一个整数值 `val` 代表节点...

    递归或迭代方法来合并两个有序链表.zip

    在编程领域,特别是数据结构和算法的学习中,"合并两个有序链表" 是一个常见的问题。这个主题涉及到链表操作,以及两种主要的解决问题的方法:递归和迭代。下面我们将详细探讨这两个方法。 首先,链表是一种数据...

    java-leetcode题解之第21题合并两个有序链表.zip

    标题中的"java-leetcode题解之第21题合并两个有序链表.zip"指的是一个Java编程语言实现的LeetCode算法题解,具体是第21题——“合并两个有序链表”。这道题目要求我们将两个已排序的链表合并为一个新的已排序链表并...

    c语言链表的基本操作之合并两个有序链表.zip

    合并两个有序链表的目的是创建一个新的链表,其中包含两个输入链表的所有元素,且新链表仍然保持排序顺序。例如,如果链表1为1-&gt;3-&gt;5,链表2为2-&gt;4-&gt;6,则合并后的链表应为1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6。 以下是合并两个有序...

    C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现

    4. **合并两个有序链表**:`MergerLikNode` 函数实现了合并两个有序链表的功能。首先检查其中一个链表是否为空,如果是,则直接返回另一个链表。然后比较两个链表头节点的值,选择较小的节点作为新链表的头部,并...

    c++ 如何合并两个有序链表

    C++ 如何合并两个有序链表 C++ 是一种高效的编程语言,它广泛应用于操作系统、嵌入式系统、游戏开发等领域。在 C++ 中,链表是一种常用的数据结构,它可以用来存储和处理大量数据。在实际应用中,我们经常需要合并...

    21合并两个有序链表.zip

    21合并两个有序链表.zip

    合并两个有序链表.md

    合并两个有序链表.md

    C#-Leetcode编程题解之第21题合并两个有序链表.zip

    在本压缩包中,主题是"C#-LeetCode编程题解之第21题合并两个有序链表",这涉及到C#编程语言以及在LeetCode平台上解决算法问题的技巧。LeetCode是一个广受欢迎的在线平台,它提供了各种编程挑战,帮助开发者提升算法...

    合并两个有序链表(java代码).docx

    ### 合并两个有序链表(Java代码) #### 背景介绍 在计算机科学中,链表是一种常用的数据结构,它由一系列节点组成,每个节点包含数据元素和指向下一个节点的指针。处理链表时,我们经常需要对它们进行排序、合并...

    c语言-c语言编程基础之leetcode题解第21题合并两个有序链表.zip

    在C语言编程中,解决LeetCode的第21题——“合并两个有序链表”是一项基本而重要的技能。这道题目旨在考察程序员对链表结构的理解以及如何在链表上执行高效的合并操作。在此,我们将深入探讨C语言中的链表概念、如何...

    c++-c++编程基础之leetcode题解第21题合并两个有序链表.zip

    第21题"合并两个有序链表"是其中一道经典的题目,它涉及到链表的操作,这对于理解和掌握C++中的链表非常重要。下面我们将详细探讨这个问题以及如何用C++解决它。 首先,我们需要理解链表的概念。链表是一种线性数据...

    python-leetcode题解之第021合并两个有序链表

    python python_leetcode题解之第021合并两个有序链表

    算法讲解010【入门】链表入门题目-合并两个有序链表.pptx

    算法讲解010【入门】链表入门题目-合并两个有序链表

    两个有序链表的合并代码

    **合并两个有序链表**意味着将两个已排序的链表合并成一个新的、同样有序的链表。 #### 代码解析 接下来,我们将逐行解析给定的C语言代码,并解释其工作原理。 1. **宏定义与头文件包含** ```c #define NULL 0 ...

Global site tag (gtag.js) - Google Analytics