LeetCode-143-重排链表 LeetCode-143-重排链表

重排链表

【LeetCode-143-重排链表】题目描述：给定一个单链表 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 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; }} }