《剑指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)
blank

相关推荐

  • 数据库中varchar类型 最大长度是多少?[通俗易懂]

    数据库中varchar类型 最大长度是多少?[通俗易懂]一.varchar存储规则:4.0版本以下,varchar(20),指的是20字节,如果存放UTF8汉字时,只能存6个(每个汉字3字节)5.0版本以上,varchar(20),指的是20字符,无论存放的是数字、字母还是UTF8汉字(每个汉字3字节),都可以存放20个,最大大小是65532字节Mysql4中最大也不过是20个字节,但是Mysql5根据编码不同,存储大小也不同。…

  • 与满二叉树完全二叉树

    与满二叉树完全二叉树

    2021年12月17日
  • OpenCV学习笔记:resize函数改变图像的大小

    OpenCV提供了resize函数来改变图像的大小,函数原型如下:void resize(InputArray src,OutputArray dst,Size dsize,double fx=0,double fy=0,int interpolation=INTER_LINEAR );先解释一下各个参数的意思:src:输入,原图像,即待改变大小的图像

  • Java后端学习路线图,你真的只需要这一张!

    Java后端学习路线图,你真的只需要这一张!原文链接前言学习路线图往往是学习一样技术的入门指南。网上搜到的Java学习路线图也是一抓一大把。今天我只选一张图,仅此一图,足以包罗Java后端技术的知识点。所谓不求最好,但求最全,学习Java后端的同学完全可以参考这张图进行学习路线安排。当然,有一些知识点是可选的,并不是说上面有的你都要会啦。我在复习秋招的过程中就是基于此图进行复习的,感觉效果还是不错的。闲言少叙,我们还…

  • docker的端口映射_docker修改端口映射

    docker的端口映射_docker修改端口映射1.downloadimage:docker@default:/root#dockerpullmikeraab/hello-earth:latest2.createandstartcontainer(docker主机IP:192.168.99.101)a)默认大写-P自动映射$docker@default:/root#dockerrun-d

    2022年10月17日
  • 如何在国外注册一家公司(免费公司注册)

    随着世界经济一体化的发展,商业越来越呈现跨国界的趋势,注册海外公司已经成为中大型企业的必选之路。举一个很简单的例子:一个企业向美国出口产品,需要申请配额及一系列的相关手续,这中间需要多花费一到两倍的成本,而如果该企业拥有一个海外离岸公司,由企业向离岸公司出口产品,再由离岸公司向美国等发达国家出口,就可以绕开关税壁垒活的免税待遇,并且还能够成功绕开出口配额限制。那如何注册一个海外公司?首先需要…

发表回复

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

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