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}.
題意：重新設(shè)置鏈表順序渠啊，要求第一個(gè)節(jié)點(diǎn)連接最后一個(gè)球散，然后最后一個(gè)連接第二個(gè)乔煞，第二個(gè)再連接倒數(shù)第二個(gè)塔拳。烁涌。。
思路：
把鏈表看做左右兩部分续滋，先找到右半部分的起始節(jié)點(diǎn)惨远。(奇數(shù)個(gè)時(shí)谜悟，右半部分起始是中間節(jié)點(diǎn)的next)。
把右半部分節(jié)點(diǎn)入棧北秽，這樣棧頂節(jié)點(diǎn)就是鏈表的尾巴葡幸。
-
從鏈表頭部開始，不斷把左半部分的節(jié)點(diǎn)和棧頂彈出的節(jié)點(diǎn)相連贺氓。
public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } //找后側(cè)的起始節(jié)點(diǎn) ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode rStart = fast == null ? slow : slow.next; //記錄右側(cè)待連接的節(jié)點(diǎn) Stack<ListNode> stack = new Stack<>(); while (rStart != null) { stack.push(rStart); rStart = rStart.next; } //連接工作 ListNode curLeft = head; while (!stack.isEmpty()) { ListNode nextLeft = curLeft.next; ListNode curRight = stack.pop(); curLeft.next = curRight; //如果下個(gè)待連接的左節(jié)點(diǎn)就是當(dāng)前連接的右節(jié)點(diǎn)蔚叨，那么此時(shí)curLeft和curRight就是鏈表中相鄰的節(jié)點(diǎn) if (nextLeft == curRight) { nextLeft = null; } curRight.next = nextLeft; curLeft = nextLeft; } if (curLeft != null) { curLeft.next = null; } }
