首页 > 代码库 > LeetCode reorder-list
LeetCode reorder-list
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes‘ values.
For example,
Given{1,2,3,4}, reorder it to{1,4,2,3}.
给定一个单链表L:L0→L1→…→ln1→Ln,
重新排序到:L0→Ln→L1→ln1→L2→Ln 2→…
你必须做这个就地在不改变节点的值。
例如,
考虑到{ 1,2,3,4 },重新排序到{ 1 4 2 3 }。
该题要先找到链表的中点，然后将中点后面的链表进行排序，排序结束以后进行 合并
package cn.edu.algorithm.huawei;import java.util.ArrayList;public class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null || head.next.next == null) return; ListNode mid = getListMid(head); ListNode reverList = reverseList(mid.next); mid.next = null; merge(head, reverList); //print(list); } public ListNode getListMid(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } public void merge(ListNode node1, ListNode node2) { ListNode cur1 = node1; ListNode cur2 = node2; ListNode temp1; ListNode temp2; while (cur1 != null & cur2 != null) { temp1 = cur1.next; cur1.next = cur2; temp2 = cur2.next; cur2.next = temp1; cur1 = temp1; cur2 = temp2; } //return node1; } public void print(ListNode list) { while (list != null) { System.out.print(list + " "); list = list.next; } System.out.println(""); } public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); node1.next = node2; node2.next = node3; ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); ListNode node6 = new ListNode(6); // node3.next = node4; // node4.next = node5; Solution s = new Solution(); s.reorderList(node1); }}class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } @Override public String toString() { return val + ""; }}class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } @Override public String toString() { return val + ""; }}
LeetCode reorder-list
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。