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}.
题意：重新设置链表顺序，要求第一个节点连接最后一个，然后最后一个连接第二个，第二个再连接倒数第二个。。。
思路：
把链表看做左右两部分，先找到右半部分的起始节点。(奇数个时，右半部分起始是中间节点的next)。
把右半部分节点入栈，这样栈顶节点就是链表的尾巴。
-
从链表头部开始，不断把左半部分的节点和栈顶弹出的节点相连。
public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } //找后侧的起始节点 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; //记录右侧待连接的节点 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; //如果下个待连接的左节点就是当前连接的右节点，那么此时curLeft和curRight就是链表中相邻的节点 if (nextLeft == curRight) { nextLeft = null; } curRight.next = nextLeft; curLeft = nextLeft; } if (curLeft != null) { curLeft.next = null; } }
