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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

class Solution {     public void reorderList(ListNode head) {         if (head == null || head.next == null)             return;         //找到链表的中点，如1 2 3 4 5 6 7 8，则p1是4         ListNode p1 = head;         ListNode p2 = head;         while (p2.next != null && p2.next.next != null) {             p1 = p1.next;             p2 = p2.next.next;         }                //链表后半边逆序，5 6 7 8 变成 8 7 6 5          ListNode preMiddle = p1; //preMiddle 是4         ListNode preCur = p1.next; //preCur 是5         while (preCur.next != null) {             ListNode cur = preCur.next; //cur是6             preCur.next = cur.next; //5->7             cur.next = preMiddle.next; //6->5             preMiddle.next = cur; //4->6         }         //达到最后排序目的         p1 = head;         p2 = preMiddle.next;         while (p1 != preMiddle) {             preMiddle.next = p2.next; //另4->7             p2.next = p1.next; //8->2             p1.next = p2;//1->8             p1 = p2.next;//让p1等于2             p2 = preMiddle.next; //p2等于7，现在链表1 8 2 3 4 7 6 5         }              } }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄