【Leetcode】143. 重排链表
2021/5/16 10:25:32
本文主要是介绍【Leetcode】143. 重排链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
// 143. 重排链表 // 给定一个单链表 L:L0→L1→…→Ln-1→Ln , // 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→… // 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
题解
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ // 链表中点 + 链表反转 + 链表合并 // 以 // 1 -> 2 -> 3 -> 5 -> 4 // 为例 // 定义middle函数,取得链表中点或者中间位置靠左的点,记为mid。 // 定义右半边链表mid.next记为rightHead,将mid到rightHead断开。 // 得到: // 1 -> 2 -> 3 // 4 -> 5 // 定义链表翻转函数reverse,将rightHead翻转,得到 // 1 -> 2 -> 3 // 5 -> 4 // 然后定义merge函数,将两个链表合并 // 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户 // 内存消耗:41.4 MB, 在所有 Java 提交中击败了19.44%的用户 class Solution { public void reorderList(ListNode head) { ListNode mid = middle(head); ListNode leftHead = head; ListNode rightHead = mid.next; mid.next = null; rightHead = reverse(rightHead); merge(leftHead, rightHead); } public ListNode middle(ListNode head) { if (head == null || head.next == null) return head; ListNode pre = head; ListNode cur = head.next; while (cur != null && cur.next != null) { cur = cur.next.next; pre = pre.next; } return pre; } public ListNode reverse(ListNode head) { if (head == null || head.next == null) return head; ListNode pre = head; ListNode mid = head.next; ListNode cur = head.next.next; pre.next = null; mid.next = pre; while (cur != null) { pre = mid; mid = cur; cur = cur.next; mid.next = pre; } return mid; } public void merge(ListNode l1, ListNode l2) { while (l1 != null && l2 != null) { ListNode l1_next = l1.next; ListNode l2_next = l2.next; l1.next = l2; l1 = l1_next; l2.next = l1; l2 = l2_next; } } }
这篇关于【Leetcode】143. 重排链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置