关于java:LeetCode143重排链表

26次阅读

共计 1452 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定一个单链表 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;
        }

    }
}