Problem
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list"s nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
Solutionclass Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return; ListNode fast = head, slow = head.next, split = head; while (fast != null && fast.next != null) { split = slow; //to split slow to next half fast = fast.next.next; slow = slow.next; } //1 2 3 4 5 //3, 3, 2 (fast, slow, split) //5, 4, 3 (fast, slow, split) //1 2 3 4 //3, 3, 2 split.next = null; ListNode l2 = reverse(slow); ListNode l1 = head; while (l2 != null) { ListNode n1 = l1.next; ListNode n2 = l2.next; l1.next = l2; l2.next = n1; l1 = n1; l2 = n2; } return; } private ListNode reverse(ListNode node) { ListNode pre = null; while (node != null) { ListNode next = node.next; node.next = pre; pre = node; node = next; } return pre; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77356.html
摘要:要找到后半部分的起點,就是用快慢指針。不過該題我們不能直接拿到中間,而是要拿到中間的前一個節點,這樣才能把第一個子鏈表的末尾置為空,這里的技巧就是快慢指針循環的條件是。注意因為不能有額外空間,我們最好用迭代的方法反轉鏈表。 Reorder List Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→...
摘要:題目鏈接題目分析給定一個數組,每一個元素是一條日志。剩余部分為全為小寫字母的字符串稱為字符日志或全為數字的字符串稱為數字日志。給定的數組中確定會至少有一個字母。遍歷完成后,對字符日志進行排序。在其后拼接數字日志數組,并返回即可。 D54 937. Reorder Log Files 題目鏈接 937. Reorder Log Files 題目分析 給定一個數組,每一個元素是一條日志。 ...
Problem You have an array of logs. Each log is a space delimited string of words. For each log, the first word in each log is an alphanumeric identifier. Then, either: Each word after the identifier...
摘要:鏈表題目的集合雙指針法找中點,分割,合并,翻轉,排序。主函數對于長度為或的鏈表,返回找到中點分割鏈表并翻轉后半段為與前半段合并。當移動到最后一個元素,正好移動到整個鏈表的頭部。 Problem Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln reorder it to: L0 → Ln → L1 → Ln-1 → L2 → L...
Problem Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { ...
閱讀 2224·2021-11-22 09:34
閱讀 1334·2021-10-11 10:59
閱讀 4427·2021-09-22 15:56
閱讀 3270·2021-09-22 15:08
閱讀 3401·2019-08-30 14:01
閱讀 773·2019-08-30 11:16
閱讀 1129·2019-08-26 13:51
閱讀 2906·2019-08-26 13:43