165. 合并两个排序链表双指针

将两个排序链表合并为一个新的排序链表. 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15->null。

双指针

这个和合并两个排序数组是一样的,两个指针就行了,只是不像vector那样简单赋值就可以了,而是要通过变换指针来连接起来,思路就是新建一个链表,通过双指针每次分离出来一个节点,把这个节点链接到新链表的后面,当一个链表遍历完之后,只需把另外一个链表剩下的整个链接到新链表的后面就行了,写起来也是不难,像链表的这种遍历和拆解都应该形成自己的一套固定的写法,会简单许多。

ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        
        
        ListNode *newhead=new ListNode(0);
        ListNode *newhead_back;
        ListNode *head1=l1;
        ListNode *head2=l2;
        ListNode *tmp1;
        ListNode *tmp2;
        
        while((head1!=NULL)&&(head2!=NULL))   //两个都不空,才进while循环
        {
            tmp1=head1;
            tmp2=head2;
            
            //tmp1->next=NULL;
            //tmp2->next=NULL;
            
            if(tmp1->val<tmp2->val)
            {
                
                head1=head1->next;
                tmp1->next=NULL;
                if(!newhead->next)
                {
                    newhead->next=tmp1;
                    newhead_back=newhead->next;
                }
                else
                {
                newhead_back->next=tmp1;
                newhead_back=newhead_back->next;
                }
                
            }
            else 
            {
                
                head2=head2->next;
                tmp2->next=NULL;
                if(!newhead->next)
                {
                    newhead->next=tmp2;
                    newhead_back=newhead->next;
                }
                else
                {
                newhead_back->next=tmp2;
                newhead_back=newhead_back->next;
                }
                
            }
        }
        
        if(head1)     //如果head1不空,把其连接到后面
        {
            newhead_back->next=head1;
            return newhead->next;
        }
        if(head2)     //如果head2不空,把其连接到后面
        {
            newhead_back->next=head2;
            return newhead->next;
        }
        
        return newhead->next;
        // write your code here
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木东居士的专栏

通过源码分析 String、StringBuffer 和 StringBuilder

18630
来自专栏卡少编程之旅

Javascript一些优雅实现

359110
来自专栏Golang语言社区

Go语言基础:深入理解 struct 内嵌 inteface

对于 struct 内嵌 inteface 的使用,我是研究好半天才搞懂,这里记录下我疑问: 1. 如何更好的理解匿名接口 // 匿名接口可以被用作变量或者...

38170
来自专栏java达人

Java 中正确使用 hashCode 和 equals 方法

在这篇文章中,我将告诉大家我对hashCode和equals方法的理解。我将讨论他们的默认实现,以及如何正确的重写他们。我也将使用Apache Commons提...

37360
来自专栏二进制文集

LeetCode 473 Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchstic...

11930
来自专栏WindCoder

Java代理2 动态代理的实现原理分析

上篇Java代理(一):代理和动态代理的基础与使用中得知通过调用静态方法Proxy.newProxyInstance()可以创建动态代理,之后会调用Invoca...

14520
来自专栏陈树义

大白话说Java泛型:入门、使用、原理

远在 JDK 1.4 版本的时候,那时候是没有泛型的概念的。当时 Java 程序员们写集合类的代码都是类似于下面这样: List list = new Arr...

35060
来自专栏java学习

面试题7(考察运算符的优先级)

请选择下面代码运行后打印的结果。 public static void main(String[]args){ int x=5; int y=3; x=x+(x...

34780
来自专栏算法修养

ZOJ 3715 Kindergarten Election

At the beginning of the semester in kindergarten, the n little kids (indexed fro...

29940
来自专栏Hongten

python开发_python代码风格(coding style)

13210

扫码关注云+社区

领取腾讯云代金券