重排链表

题目描述：给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：链表遍历

首先，如果链表为空或链表只有一个节点，直接返回。

否则，首先用一个栈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;
        }

    }
}

【每日寄语】 人不怕有理想，不怕有梦想。也不管它又多大，又有多远！只要你客观的认清自己，在道德规范之内，坚持自己，做你想做的，一定会有收获的那一天！