【剑指Offer(专项突破)】026. 重排链表(Java实现) 详细解析

2024-07-16 16:26| 来源: 网络整理| 查看: 265

题目：

leetcode题目连接：力扣

分析：

Java代码实现：

注意：

复杂度分析：

代码执行结果：

题目：

给定一个单链表 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]

leetcode题目连接：力扣

分析：

将这题拆分可分为三步：

（1）将链表分别前半和后半部分，需要找到中点并进行拆分

（2）将后半部分链表进行反转

（3）按照一个前半部分结点，一个后半部分结点进行排序

因此涉及到三个方法，方法1（midList）是寻找链表中点的方法，方法2（reverseList）可参考题024. 反转链表

方法3（mergeList）这里需要另外设计

Java代码实现： /** * 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; } * } */ class Solution { public void reorderList(ListNode head) { ListNode l1 = head; ListNode midNode = midList(head); ListNode temp = midNode.next; midNode.next = null; //对链表进行拆分 ListNode l2 = reverseList(temp); mergeList(l1,l2); } //寻找链表中点 public ListNode midList(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next !=null){ slow = slow.next; fast = fast.next.next; } return slow; } //链表的反转 public ListNode reverseList(ListNode head){ if(head == null || head.next == null){ return head; } ListNode P = reverseList(head.next); head.next.next = head; head.next = null; return P; } //链表的合并 public void mergeList(ListNode l1, ListNode l2){ ListNode temp1; ListNode temp2; while(l1 != null && l2 !=null){ temp1 = l1.next; //在连接下一个新结点前需要先保存一下原结点，防止丢失 l1.next = l2; temp2 = l2.next;//在连接下一个新结点前需要先保存一下原结点，防止丢失 l2.next = temp1; l1 = temp1; l2 = temp2; } } }

注意：

在涉及到多个步骤时，最好设置不同的方法进行调用，这样思路更加清晰

复杂度分析：

时间复杂度：O（N），N为链表的结点数量

空间复杂度：O（1）

代码执行结果：

以上为个人做题笔记，很多是自己的理解，若有错误还请各位大佬指出～

【本文地址】

公司简介

联系我们