重排链表
题目形容：给定一个单链表 L 的头节点 head ，单链表 L 示意为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：链表遍历
首先，如果链表为空或链表只有一个节点，间接返回。
否则，首先用一个栈nodes记录所有的节点，并记录链表节点的数量count；
而后，记录插入的程序，遍历到奇数位时，从头结点方向插入链表；遍历到偶数位时，从栈中取出节点（即从尾结点方向）插入链表。
import com.kaesar.leetcode.ListNode;import java.util.Stack;public class LeetCode_143 { public static void reorderList(ListNode head) { if (head == null || head.next == null) { return; } // 所有节点 Stack<ListNode> nodes = new Stack<>(); // 链表节点的数量 int count = 0; ListNode cur = head; while (cur != null) { count++; nodes.push(cur); cur = cur.next; } int front = 1, back = 0, i = 1; ListNode newCur = head; cur = head.next; // 别离从头结点和栈中遍历链表节点，而后按指定程序插入新的头节点形成的链表中 while (front + back < count) { i++; if (i % 2 == 1) { // 插入正向的节点 newCur.next = cur; cur = cur.next; front++; } else { // 插入前面的节点 newCur.next = nodes.pop(); back++; } newCur = newCur.next; } // 最初，要将新的尾结点的next指向null newCur.next = null; } public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); head.next.next.next.next = new ListNode(5); System.out.println("-----重排之前-----"); ListNode cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); reorderList(head); System.out.println("-----重排之后-----"); cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } }}【每日寄语】 人不怕有现实，不怕有幻想。也不论它又多大，又有多远！只有你主观的认清本人，在道德规范之内，保持本人，做你想做的，肯定会有播种的那一天！