This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First of all, I would like to clarify that every algorithm problem has multiple solutions. We will only talk about several excellent solutions in LeetCode, hoping to help you. Let’s first look at the description of the problem

I. Title Description:

Given a single linked list L: L0→L1→… L0→Ln -1→ L1→ ln-1 →L2→ ln-2 →… You can’t just change the values inside a node, you need to actually swap nodes. Example 1:

Given linked list 1->2->3->4, rearrange as 1->4->2->3.Copy the code

Example 2:

Given linked list 1->2->3->4->5, rearrange as 1->5->2->4->3.Copy the code

Ii. Analysis of Ideas:

Because linked lists do not support subscript access, we cannot randomly access elements anywhere in the list.

Therefore, it is easy to think of a way to store the linked list using a linear table, and then to take advantage of the subscript access of linear tables, directly access the specified elements in order, and rebuild the list

Third, code demonstration

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while(node ! =null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null; }}Copy the code

Fourth, complexity analysis

Time complexity: O(N)O(N), where NN is the number of nodes in the linked list.

Space complexity: O(N)O(N), where NN is the number of nodes in the linked list. Mainly the overhead of linear tables

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together