Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

Topic describes

Given a head node head of singly linked list L, singly linked list L can be expressed as:

L0 → L1 →… → Ln -1 → Ln Please rearrange it into:

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

You can’t just change the values inside a node, but you need to actually swap nodes.

Thought analysis

The simplest idea is to keep deleting nodes and hanging them on another linked list

pre -> next = node -> next; , node -> next =secondNode; secondNode = node;Copy the code

Finally, merge the two lists.

The disadvantages of this approach are obvious. One is that it takes three traversals (because it takes one traversal to find half of the locations), and the other is that it requires extra memory.

For how to find the half position, we can use the fast and slow pointer to calculate.

For extra memory, we do a reverse of the second half of the list and then merge it

The specific implementation

Code for flipping lists

ListNode* reverseList(ListNode* head) {
    ListNode* tmp = head;
    ListNode* node = nullptr;
    while(tmp ! =nullptr) {
        ListNode* ptr = tmp->next;
        tmp->next = node;
        node = tmp;
        tmp = ptr;
    }
    return node;

}

Copy the code

conclusion

One difficulty of this problem is to find the location of each inserted node. Here, we can actually record all the nodes of the linked list in an array through one traversal, and then insert the linked list according to the index value of the array. This is equivalent to eliminating the need to calculate positions based on fast and slow Pointers and flip lists.

In addition, there is a simple way to flip the linked list, you can put it on the stack, using the last in first out of the stack to realize the flip of the linked list.

When you do algorithmic problems, it’s ok to have a solution, but it’s not a bad thing to know more solutions