# CodeTop supplementary question 1 Sort odd ascending even descending linked list

## Topic source

Supplementary question 1 Sort odd ascending even descending linked list

## Title details

Let's take a look at the original narration of several face scriptures

• In the linked list, the odd position increases in order and the even position decreases in order. How can the linked list grow from small to large? (2020.10 byte runout - back end) [2]

• Reordering combination of parity and reverse order linked list, for example: 18365472 (2020.08 byte runout - back end) [3]

• 1 - > 4 - > 3 - > 2 - > 5 given that the odd part of a linked list increases and the even part decreases, it is required to turn the linked list into an increase within O(n) time complexity, about 5 minutes (2020.07 byte jump - Test and development) [4]

• A linked list with odd bits in ascending order and even bits in descending order requires the sorting of time O(n) and space O(1)? (2020.07 byte runout - back end) [5]

It can be seen that both the back-end and test development have been investigated, and this problem is not a hard problem. We must pay attention!!

Given a linked list with odd bits in ascending order and even bits in descending order, reorder it.

Input: 1 - > 8 - > 3 - > 6 - > 5 - > 4 - > 7 - > 2 - > null
Output: 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7 - > 8 - > null

## Problem solving analysis

1. This problem is a typical linked list type of problem. The problem involves more operations, but it won't be difficult.
2. Considering that there are two types of nodes in the original linked list, namely odd nodes and even nodes, we can use two linked lists to store them respectively to better solve the problem.
3. After splitting the linked list into odd and even linked list, because the original even linked list is in descending order, we need to flip it first to turn it into an ascending linked list.
4. Finally, the two linked lists are ordered, so we can easily merge the two linked lists to sort the linked list.
5. It should be noted that I use a lot of [virtual node], which is a very useful skill often used to solve the linked list problem. It can keep us getting the head node at any time. However, when using virtual nodes, we need to be vigilant at all times. We need to assign null at the end of the virtual linked list, otherwise the linked list will be incorrect and there will be an endless loop during traversal.
```package com.walegarrett.interview;

/**
* @Author WaleGarrett
* @Date 2022/2/6 10:06
*/

import java.util.List;

/**
* Given a linked list with odd bits in ascending order and even bits in descending order, reorder it.
*  Input: 1 - > 8 - > 3 - > 6 - > 5 - > 4 - > 7 - > 2 - > null
*  Output: 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7 - > 8 - > null
*/

public class Sorting_Ascending_Descending_List {
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public static void main(String[] args) {
int[] input = {1, 8, 3, 6, 5, 4, 7, 2};
ListNode dumyOri = new ListNode(-1);
ListNode ori = dumyOri;
for(int i=0; i<input.length; i++){
ori.next = new ListNode(input[i]);
ori = ori.next;
}
ori = null;

ListNode res = sortList(dumyOri.next);
while(res != null){
System.out.print(res.val + ", ");
res = res.next;
}
}
// First split the parity linked list
ListNode dumyOdd = new ListNode(-1);
ListNode odd = dumyOdd;

ListNode dumyEven = new ListNode(-1);
ListNode even = dumyEven;

while(now != null){
if((now.val & 1) == 1){
odd.next = now;
odd = odd.next;
}else{
even.next = now;
even = even.next;
}
now = now.next;
}
odd.next = null;// Set tail node to null
even.next = null;// Set tail node to null

// Then flip the even linked list
even = reverseList(dumyEven.next);
odd = dumyOdd.next;

// Finally, merge the parity linked list
return mergeList(odd, even);
}

ListNode pre = null, now = head;
while(now != null){
ListNode temp = now.next;
now.next = pre;
pre = now;
now = temp;
}
return pre;
}

private static ListNode mergeList(ListNode odd, ListNode even){
ListNode dumyList = new ListNode(-1);
ListNode now = dumyList;
while(odd != null || even != null){
if(odd == null){
now.next = even;
even = even.next;
}else if(even == null){
now.next = odd;
odd = odd.next;
}else{
if(even.val <= odd.val){
now.next = even;
even = even.next;
}else{
now.next = odd;
odd = odd.next;
}
}
now = now.next;
}
return dumyList.next;
}
}
```