《剑指offer》– 链表中倒数第k个节点、反转链表、合并两个排序的链表

《剑指offer》– 链表中倒数第k个节点、反转链表、合并两个排序的链表

一、链表中倒数时第k个节点:

1、题目:

输入一个链表,输出该链表中倒数第k个结点。

2、解题思路:单链表具有单向移动的特性。

(1)第一种:先遍历链表,算出链表节点数count,第二次直接遍历到第count-k个节点。但是要注意,可能链表节点数count小于k,此时要返回NULL,所以要先判断这个条件。(这一种就不贴代码出来了)

(2)第二种:

可以用两个指针,一个指针遍历到第k个结点的时候,第二个指针再走到第一个节点,然后两个指针的距离始终保持k-1,这样,当第一个指针的next==NULL,也就是走到最后一个节点的时候,第二个指针对应的位置,就是倒数第k个结点。

这样的好处是能够节省一个循环,时间复杂度会相应降低。从Q(2N) 到Q(N)

注意,但是需要一个小循环让第一个指针先走到第k个指针。同时也存在结点总数小于k的问题,如果循环还没有进行到k次,而第一个指针的已经是NULL,即走到头了,那么,函数返回NULL。

3、代码实现:

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

        if(head ==null || k<=0){
            return null;
        }
        ListNode last=head;
        
        //第一个指针先移动k-1个节点
        for(int i=0;i<k-1;i++){
            if(head.next!=null){
                head=head.next;
            }else{
                return null;
            }
        }
        //同时移动两个指针,当第一个指针指向null的时候,last就是所求的结点
        while(head.next!=null){
            head=head.next;
            last=last.next;
        }
        
        return last;
    }
}

 

 

二、反转链表:

参考博客:https://www.jianshu.com/p/e385d9c06672

1、题目:

输入一个链表,反转链表后,输出新链表的表头。

2、解题思路:

2-1:第一种:使用递归方式:

(1)解题思路:

假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表。
如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转后链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给head->next->next指针,并且一定要记得让head->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层head->next->next赋值的时候会覆盖后续的值。依次反转。。

《剑指offer》-- 链表中倒数第k个节点、反转链表、合并两个排序的链表

(2)代码实现:

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //递归方式
        if(head==null || head.next==null){
            return head;
        }
        ListNode newList=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        
        return newList;
    }
}

 

2-2第二种:使用迭代方式:

(1)解题思路:

先给定一个空的链表newList,然后判断传入的链表head是不是空链表或者链表元素只有一个,如果是,直接返回就可以。如果不是,则对链表进行迭代,然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp,就这样一直迭代完整个链表,返回newList就可以。如下图所示:

《剑指offer》-- 链表中倒数第k个节点、反转链表、合并两个排序的链表

(2)代码实现:

 public ListNode ReverseList(ListNode head) {
        
        //非递归方式:
        ListNode newList=null;
        if(head==null || head.next==null){
            return head;
        }
        
        while(head!=null){
            ListNode temp=head.next;
            head.next=newList;
            newList=head;
            head=temp;
        }
        return newList;
    }

 

 

三、合并两个排序的链表:

参考博客:https://blog.csdn.net/qq_23217629/article/details/51730312

1、题目:

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

2、解题思路:

比较两个链表的第一个节点,取出最小值的节点,接着再按照相同的方式重复比较剩余链表的节点。

3、代码实现:


public class Solution {
    public ListNode Merge1(ListNode list1, ListNode list2) {
            //递归版本
			ListNode head;
			if (list1 == null) {
				return list2;
			}
			if (list2 == null) {
				return list1;
			}
			if (list1.val < list2.val) {
				head = list1;
				head.next = Merge(list1.next, list2);
			} else {
				head = list2;
				head.next = Merge(list1, list2.next);
			}
			return head;
		}

    public ListNode Merge(ListNode list1,ListNode list2) {
		//非递归版本:
		ListNode head = new ListNode(-1);//头节点,用来存储合并的链表
		head.next = null;
		ListNode root = head;//root暂存我新建的头节点,合并之后返回root.next,就是题目给的头节点
		
		while(list1!=null && list2!=null){
			if(list1.val <=list2.val){
				head.next=list1;
				head = list1;
				list1 = list1.next;
			}else{
				head.next=list2;
				head=list2;
				list2=list2.next;
			}
		}
		
		//把未结束的链表连接到合并后的链表尾部
		if(list1 !=null){
			head.next=list1;
		}
		if(list2 !=null){
			head.next=list2;
		}
		
		return root.next;
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114699.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • JDK下载与安装教程

    JDK下载与安装教程学习JAVA,必须得安装一下JDK(javadevelopmentkitjava开发工具包),配置一下环境就可以学习JAVA了,下面是下载和安装JDK的教程:1.JDK下载地址:http://www.oracle.com/technetwork/java/javase/downloads/index.html点开链接你应该看到如下图所示的界面:2.点击上图中箭头所指的地方,会出

  • python中random函数的使用方法 详解

    python中random函数的使用方法 详解#random各种使用方法importrandom#随机生成[0.1)的浮点数print("random():",random.random())#随机生成1000-9999之间的整数print("randint(1000,9999):",random.randint(1000,9999))#随机生成0-20之间的偶数print("randrange(0,21,2):"…

  • Asp.net中文本框全选

    Asp.net中文本框全选Asp.net中文本框全选

  • dsp28335复位电路_28335串口不能中断

    dsp28335复位电路_28335串口不能中断0前言本期实验目标:采用外部中断方式响应按键触发,实现LED电平反转。外部中断是DSP十分常用的功能,通常用来响应一些控制操作,比如判断按键是否按下,传感器是否接收到信号等等。那么通过该例程,大家则可以快速学会使用外部中断的功能!本节仍然将分为硬件部分、软件部分和实验展示三个方面进行介绍。1硬件部分DSP28335支持XINT1-XINT7和XNMI共8路外部中断源,其中中断源XINT1/2和XNMI可以设定为从GPIO端口A的任意一个管脚输入,即GPIO0-GPIO31。而XINT3/4/5/

  • 开挂网站免费版_开心ol辅助脚本

    开挂网站免费版_开心ol辅助脚本开讲。做一个Web游戏外挂需要的准备知识:1)需要有耐心2)熟悉HTML,JavaScript,特别是FORM3)熟悉HTTP协议,特别是Cookie,URL的编码方式和POST,GET内容格式4)熟悉游戏本身,能抽象出最优的赚钱/升级的数学模型5)掌握一门语言,白菜萝卜都可以,我比较喜欢用Python和C#6)需要一些抓包的工具,比如Fiddle…

  • nodejs搭建MQTT服务器

    nodejs搭建MQTT服务器前言mqtt协议介绍一mqtt协议介绍二图片来自https://www.jianshu.com/p/9e74287e3b07正文安装nodejs下载安装即可。安装mqtt.js模块新建一个文件夹,打开cmd,npminstallmqtt–save,这里很有可能能会报错,百度一下就可以解决。安装好mqtt.js模块后,文件夹中会多两个文件出来。搭建服务器mqttser…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号