Topic source

Supplementary question 1 Sort odd ascending even descending linked list

Title details

This article is a supplement to the enterprise question bank CodeTop[1], summarizing those high-frequency interview questions that can not be found on Leetcode.

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;
        }
    }
    public static ListNode sortList(ListNode head){
        // First split the parity linked list
        ListNode dumyOdd = new ListNode(-1);
        ListNode odd = dumyOdd;

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

        ListNode now = head;
        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);
    }

    private static ListNode reverseList(ListNode head){
        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;
    }
}