牛客网刷题

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

问题描述

将给定的单链表 L： L0→L1→…→L{n-1}→Ln 重新排序为：L0→Ln →L1→L{n-1}→L2→L{n-2}→…L 要求使用原地算法，不能改变节点内部的值，需要对实际的节点进行交换。

示例示例1

输入 {10,20,30,40}

输出 {10,40,20,30}

解决思路思路线性表：因为链表没有下表，我们可以现将链表遍历一遍，存储到线性表中，然后再重排序链表中点+链表逆序+合并链表：先查找链表的中点，将链表分开，后半截链表逆序，然后合并两个两表，即可重排序代码实现思路1:线性表 // 思路1：线性表 public class Solution { public void reorderList(ListNode head) { // 因为有坐标对应关系，所以使用数组或list解决 List temp = new ArrayList(); while (head != null) { temp.add(head); head = head.next; } for (int i = 0; i temp.get(temp.size() - i - 1).next = temp.get(i + 1); } } } }

时间复杂度分析： O(N)：遍历链表

空间复杂度分析： O(N)：使用了大小为N的线性表

思路2:链表中点+链表逆序+合并链表 // 思路2:链表中点+链表逆序+合并链表 public class Solution { //寻找链表中点 + 链表逆序 + 合并链表 public void reorderList2(ListNode head) { if (head == null) { return; } // 获取中点 ListNode middle = getMiddle(head); // 分离 ListNode next = middle.next; middle.next = null; // 反转 ListNode revert = revert(next); // 合并 merge(head, revert); } // 查找中点 public ListNode getMiddle(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 revert(ListNode head){ ListNode pre = null; // 包含一个前置节点，记录已经头插的 ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; // 先更改当前节点的next节点 pre = cur; // pre节点为当前节点 cur = next; // 当前节点为next节点 } return pre; } public ListNode merge(ListNode l1, ListNode l2){ ListNode l1_tmp; ListNode l2_tmp; while (l1 != null && l2 != null) { l1_tmp = l1.next; l2_tmp = l2.next; l1.next = l2; l1 = l1_tmp; l2.next = l1; l2 = l2_tmp; } return l1; } }

时间复杂度分析： O(N)：遍历链表

空间复杂度分析： O(1)：没有使用额外的空间

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

重排链表-牛客网

【本文地址】

公司简介

联系我们