首页 > 代码库 > 143. Reorder List
143. Reorder List
不定期更新leetcode解题java答案。
采用pick one的方式选择题目。
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
如题意，按照如上方式将单链表重新排序。由于单链表的特性，如果用正常方式逐个改变链表位置，需要做多次遍历获取节点信息。因此，首先将后半链表倒序处理，再将分开的两条链表进行链接。
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public void reorderList(ListNode head) {11 //count nodes 12 ListNode node = head;13 int count = 0;14 while(node != null){15 count++;16 node = node.next;17 }18 if(count <= 1)19 return;20 21 //get middle node22 ListNode last = null;23 ListNode now = head;24 for(int i = 0; i < count / 2; i++){25 if(i == count / 2 - 1){26 ListNode tmp = now.next;27 now.next = null;28 now = tmp;29 }else30 now = now.next;31 }32 ListNode next = now.next;33 //reverse the nodes after the mid node34 while(next != null){35 ListNode tmp = next.next;36 now.next = last;37 last = now;38 now = next;39 next = tmp;40 }41 now.next = last; //need point one more time42 43 ListNode mid = now; //the new middle node after reverse44 45 node = head;46 //combine two linked lists47 while(node != null){48 ListNode tmp = node.next;49 50 node.next = mid;51 node = tmp;52 53 tmp = mid.next;54 if(node != null)55 mid.next = node;56 mid = tmp;57 }58 }59 }
由于本题要求不允许直接改变链表数值，不应采用此方法，亦将代码贴上，测试可得下述代码时间消耗更长：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public void reorderList(ListNode head) {11 ListNode node = head;12 ArrayList<Integer> list = new ArrayList();13 while(node != null){14 list.add(node.val);15 node = node.next;16 }17 18 for(int i = 0; i < list.size(); i++){19 head.val = i % 2 == 0 ? list.get(i / 2) : list.get(list.size() - 1 - i / 2);20 head = head.next;21 }22 }23 }
143. Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。