preface

Ordered list of the merger of this series of questions in the interview is also more common, so summarize the relevant questions

  1. NC33 Merge ordered Lists (simple)
  2. NC51 Merge k sorted lists (difficult)
  3. NC70 Single linked list sort (simple)

Merge ordered lists

Description: merge two ordered lists into a new list, requiring that the new list is generated by concatenating the nodes of the two lists, and that the new list remains in order after the merge.

Create a virtual head node, and then iterate through two ordered lists, using the node with the smaller val as the next node, until any list is empty, and then the list with the completed traversal

AC code:

    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        
        ListNode ans = new ListNode(-1);
        ListNode cur = ans;
        
        while(l1 ! =null&& l2 ! =null) {if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return ans.next;
    }
Copy the code

Merge k sorted lists

Merge k sorted lists and return them as one sorted list.

  • Borrow mergeTwoLists method in merging ordered linked list to add K lists to the queue. When the size of the queue is greater than 1, take out 2 lists to merge, and add them to the list after merging, and loop until the size of the queue is 1

  • Using a priority queue, build a small root heap and put the top nodes into it. Each heap is topped with the smallest node, which is pulled out in turn, and then put its next node back

AC code:

Traverse the merger

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> queue = new LinkedList<>();
        for(ListNode node : lists) queue.offer(node);
        
        while(queue.size() ! =1){
            ListNode l1 = queue.poll();
            ListNode l2 = queue.poll();
            
            queue.offer(mergeTwoLists(l1, l2));
        }
        return queue.poll();
    }
Copy the code

The version that uses the priority queue

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> queue = new PriorityQueue<>((a,b)-> a.val - b.val);
        
        ListNode ans = new ListNode(-1);
        ListNode cur = ans;
        
        for(ListNode node : lists){
            if(node ! =null){ queue.offer(node); }}while(! queue.isEmpty()){ ListNode node = queue.poll(); cur.next = node; cur = cur.next;if(node.next ! =null){ queue.offer(node.next); }}return ans.next;
    }
Copy the code

Sorting of single linked list

Description: Given an unordered singly linked list, implement the sorting of the singly linked list (sorted in ascending order).

Thinking analysis: use the fast and slow pointer to find the middle node of the list, and then divide the list into two parts, recursion until there is only one node, and then sort and merge from the bottom up, borrow the mergeTwoLists method in the list merging

Tip: The use of only two nodes is divided because the middle node is divided into the first part

AC code:

    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null) {return head;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while(fast ! =null&& fast.next ! =null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rightStart = slow.next;
        slow.next = null;
        
        ListNode leftSort = sortInList(head);
        ListNode rightSort = sortInList(rightStart);
        
        return mergeTwoLists(leftSort, rightSort);
    }

Copy the code