LCR 026

题目：LCR 026

解法一：线性表

将链表中所有元素加入数组中，创建两个指针，分别指向数组的头部和尾部，然后向中间遍历

    public void reorderList(ListNode head) {if (head == null || head.next == null || head.next.next == null) return;List<ListNode> list = new ArrayList<>();ListNode cur = head;while (cur != null) {list.add(cur);cur = cur.next;}ListNode reorderNode = new ListNode(0, head);for (int i = 0; i < list.size(); i++) {int index1 = i, index2 = list.size() - 1 - i;ListNode start = list.get(index1);ListNode end = list.get(index2);if (index1 == index2) {reorderNode.next = start;start.next = null;break;} else if (index1 == index2 - 1) {reorderNode.next = start;start.next = end;end.next = null;break;} else {reorderNode.next = start;start.next = end;reorderNode = end;}}}

解法二：寻找链表中点 + 链表逆序 + 合并链表

    public void reorderList(ListNode head) {if (head == null || head.next == null || head.next.next == null) return;ListNode middleNode = middleNode(head);ListNode reversedList = reverseList(middleNode);mergeList(head, reversedList);}public ListNode mergeList(ListNode head1, ListNode head2) {if (head1 == null || head2 == null) return head1;ListNode dummy = new ListNode(0), prev = dummy, node1 = head1, node2 = head2;while (node2 != null) {if (node1 == node2) {prev.next = node2;break;}ListNode nextNode1 = node1.next;ListNode nextNode2 = node2.next;prev.next = node1;node1.next = node2;prev = node2;node1 = nextNode1;node2 = nextNode2;}return dummy.next;}public ListNode middleNode(ListNode head) {if (head == null || head.next == null) return head;ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}public ListNode reverseList(ListNode head) {ListNode prev = null, cur = head, next;while (cur != null) {next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}