【Java|golang】143. 重排链表---快慢指针

这篇具有很好参考价值的文章主要介绍了【Java|golang】143. 重排链表---快慢指针。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[1,4,2,3]
示例 2:

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]

提示:

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

    public void reorderList(ListNode head) {
        //使用快慢指针找到中间节点
        ListNode slow=head,fast=slow.next;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //后一半反转
        ListNode lastHalf = reverserLastHalf(slow.next);
        slow.next=null;
        ListNode preHalf=head;
        while (lastHalf!=null){
            ListNode preTemp = preHalf.next;
            ListNode lastTemp = lastHalf.next;
            preHalf.next=lastHalf;
            lastHalf.next=preTemp;
            preHalf=preTemp;
            lastHalf=lastTemp;
        }
    }
    public ListNode reverserLastHalf(ListNode head) {
        ListNode start=null,temp=null;
        while (head!=null){
           temp=head.next;
           head.next=start;
           start=head;
           head=temp;
        }
        return start;
    }

【Java|golang】143. 重排链表---快慢指针,指针,golang,java,golang,链表

 public  void reorderList(ListNode head) {
			ListNode p=head;
			List<ListNode> list=new ArrayList<ListNode>();
			p=head;
			while(p!=null) {
				list.add(p);
				p=p.next;
			}
			if(list.size()>1) {
                ListNode p1=list.get(list.size()-1);
                ListNode p2;
			p=head;
			for(int i=1;i<=(list.size()+1)/2-1;i++) {
				p2=p.next;
				p.next=p1;
				p=p1;
				p.next=p2;
				p1=list.get(list.size()-1-i);
				p1.next=null;
				p=p2;
				
			}
            }
			
	        
	    }
func reorderList(head *ListNode)  {
	//使用快慢指针找到中间节点
	slow,fast:=head,head.Next
	for fast!=nil&&fast.Next!=nil{
		slow=slow.Next
		fast=fast.Next.Next
	}
	//后一半反转
	lastHalf := reverserLastHalf(slow.Next)
	//合并
	slow.Next=nil
	preHalf:=head
	for lastHalf!=nil{
		preTemp := preHalf.Next
		lastTemp := lastHalf.Next
		preHalf.Next=lastHalf
		lastHalf.Next=preTemp
		preHalf=preTemp
		lastHalf=lastTemp
	}
}

func reverserLastHalf(head *ListNode) *ListNode {
    var start,temp *ListNode
	for head!=nil{
		temp=head.Next
		head.Next=start
		start=head
		head=temp
	}
	return start
}

【Java|golang】143. 重排链表---快慢指针,指针,golang,java,golang,链表文章来源地址https://www.toymoban.com/news/detail-621572.html

到了这里,关于【Java|golang】143. 重排链表---快慢指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode算法小抄 -- 链表(快慢指针、双指针、回文链表)

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计10077字,阅读大概需要10分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ Collection 子接口之 Queue (LeetCode上经常用,手撕算法题!

    2023年04月08日
    浏览(42)
  • 链表刷题常用技巧——快慢指针

    强大,不动如山的强大,不会输给自己的真正的强大。  往期回顾: 数据结构——单链表 单链表力扣刷题 文章目录 经典例题:链表的中间结点 题目分析及双指针思路引入  双指针图解 leetcode 核心代码 判断环形链表——快慢指针延伸为追及问题 题目分析,图解 leetcode 核心

    2024年02月14日
    浏览(39)
  • 【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表

      目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、快慢指针反转链表   原题链接:  234. 回文链表 - 力扣(LeetCode) 示例 1: 输入: head = [1,2,2,1] 输出: true  示例 2: 输入: head = [1,2] 输出: false  提示:  链表中节点数目在范围[1, 10^5] 内 0 = Node.val = 9 进阶: 你能否用

    2024年02月08日
    浏览(45)
  • 环形链表 II(力扣142)(快慢指针)

    142.环形链表—力扣 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到

    2023年04月25日
    浏览(40)
  • 快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战

    很多同学都听过 快慢指针 这个名词,认为它不就是定义两个引用(指针)一前一后吗?是的,它的奥秘很深,它的作用究竟有哪些?究竟可以用来做哪些题目?下面我将一一带你了解和应用 下面的本节的大概内容,有疑惑的点,欢迎小伙伴们留言 目录 1.简述快慢指针 2.快慢

    2024年02月04日
    浏览(35)
  • 力扣hot100 环形链表 快慢指针 哈希 数学公式

    Problem: 142. 环形链表 II 👨‍🏫 参考题解 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月23日
    浏览(71)
  • 【C/C++数据结构】链表与快慢指针

    目录 一、单链表 二、双向循环链表 三、判断链表是否带环 四、链表的回文结构判断 五、复制带随机指针的链表 优点 :头部增删效率高,动态存储无空间浪费 缺点 :尾部增删、遍历效率低,不支持随机访问节点 头结点 :单链表头结点可有可无,带头结点更方便进行初始

    2024年02月16日
    浏览(91)
  • LeetCode - 142. 环形链表 II (C语言,快慢指针,配图)

            如果你对快慢指针,环形链表有疑问,可以参考下面这篇文章,了解什么是环形链表后,再做这道题会非常简单,也更容易理解下面的图片公式等。 LeetCode - 141. 环形链表 (C语言,快慢指针,配图)-CSDN博客         上述文章总结: 如果一个链表是环形链表,采用

    2024年02月05日
    浏览(59)
  • 【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表

    环形链表 Ⅱ【LC142】 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(

    2024年02月15日
    浏览(58)
  • LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】

    前言 本文总结了力扣141.环形链表|以及142.环形链表||这两道有关环形链表的求解方案,去求证链表是否带环已经如何找出入环口的结点。 有关环形链表,在BAT等大厂面试中均有出现,一般是属于 中等难度 的题,需掌握 原题传送门 给你一个链表的头节点 head ,判断链表中是

    2024年02月01日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包