首页 > 代码库 > [Leetcode][JAVA] Reorder List
[Leetcode][JAVA] 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}.
比较容易思考且实现的一个思路是， 将链表从中心拆成两半，后一半全部反向连接，然后前一半和后一半一个一个节点交替连接。
拆分阶段使用快慢指针方法即可得到两个平分的链表。
反向和合并阶段就是很常规的链表操作。
代码：
1 public void reorderList(ListNode head) { 2 if(head==null || head.next==null) 3 return; 4 //split 5 ListNode fast = head; 6 ListNode slow = head; 7 while(true) 8 { 9 fast = fast.next.next;10 if(fast==null || fast.next==null)11 break;12 slow = slow.next;13 }14 fast = slow.next;15 slow.next = null;16 slow = head;17 //reverse fast18 fast = reverse(fast);19 //insert20 while(slow!=null && fast!=null)21 {22 ListNode snext=slow.next;23 ListNode fnext=fast.next;24 slow.next=fast;25 if(snext!=null)26 fast.next=snext;27 slow = snext;28 fast = fnext;29 }30 }31 public ListNode reverse(ListNode head)32 {33 ListNode cur = head;34 ListNode pre = null;35 while(cur!=null)36 {37 ListNode temp = cur.next;38 cur.next = pre;39 pre = cur;40 cur = temp;41 }42 return pre;43 }
[Leetcode][JAVA] Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。