Remove Nth Node From End of List, Merge Two Sorted Lists, Merge K Sorted Lists

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

Honestly I don’t know how my first solution got accepted, basically I just count the size of list and then remove that element in the second pass.

public ListNode removeNthFromEnd(ListNode head, int n) {
           ListNode cur=head;
           int i=0;
           while(cur!=null){cur=cur.next;i++;}
           System.out.println(i);
           ListNode cur2=head;
            
           if(n==i){head=head.next;}
            
           for(int j=0;j<i-n-1;j++){
               
               System.out.println(j);
               cur2=cur2.next;
           }
           if (cur2.next == null) {
               return null;
           }
           else cur2.next=cur2.next.next;
           
           return head;      
       }

One pass solution using two pointers: one fake pointer to move n steps from the beginning, then move both pointers until list ends.

public ListNode removeNthFromEnd(ListNode head, int n) {
     
         ListNode cur=head;
         ListNode p=head;
         
         for(int i=0;i<n;i++){cur=cur.next;}
         //deal with removing head cases
         if(cur==null) head=head.next;
         //made a mistake here, forgot to move cur with p...
         else {while(cur.next!=null){p=p.next;cur=cur.next;}
         p.next=p.next.next;}
         return head;
    }

---

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution

Note: Algorithm is trivial, however I always forget to copy head to last therefore lost the final head during the iteration…

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode h=new ListNode(0);
        ListNode l=h;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                l.next=l1;
                l1=l1.next;     
            }
            else{
                l.next=l2;
                l2=l2.next;
            }
            l=l.next;
        }
        //attach the rest of one list
        if (l1==null) l.next=l2;
        else l.next=l1;
        return h.next;
    }

---

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution

First Solution is Divide and Conquer, by calling the above method and reconstruct. The recursion is T(k) = 2T(k/2)+O(n*k)=O(nklogk).

public ListNode mergeKLists(List<ListNode> lists) {
         
         int n=lists.size();
         if(n==0) return null;
         //main function call
         else return mergeKlist(lists,0,n-1);
         
     }
     
     public ListNode mergeKlist(List<ListNode> lists, int l, int r){
         
         if(l<r){
             int m=(l+r)/2;
             //divide the lists by 2 until its size reaches 1, then merge them from bottom to top
             return mergeTwoLists(mergeKlist(lists,l,m),mergeKlist(lists,m+1,r));
         }
         
         return lists.get(l);
       }

Or, instead of dividing into two parts, we can use ArrayDeque Class. (Similar to brute force solution, merges two list each time, whose complexity is n(2+3+…k)=O(nk^2))

public ListNode mergeKLists(List<ListNode> lists) {
    
      if(lists == null || lists.isEmpty()) return null;
      ArrayDeque<ListNode> q = new ArrayDeque<ListNode>();
      for(ListNode n : lists) {
          if (n != null) q.offer(n);
      }
      while(q.size() > 1) {
          ListNode a = q.poll();
          ListNode b = q.poll();
          q.offer(mergeTwoLists(a, b));
      }
      
      return q.poll();
 }

Second Solution is PQ. We can add the heads of all lists into the queue. And we can poll out the smallest one. If the next node of this smallest node is not null, we can add the next node to the queue. Until we empty the PQ, we get the sorted lists. The complexity is also O(nklogk).

public ListNode mergeKLists(List<ListNode> lists) {
         if(lists == null || lists.isEmpty()) return null;
         PriorityQueue<ListNode> heap=new PriorityQueue<>(lists.size(), new Comparator<ListNode>(){
            public int compare(ListNode a, ListNode b){
                if(a==null) return 1;
                if(b==null) return -1;
                return a.val - b.val;
            }
            });
        for(int i=0; i<lists.size(); i++){
            if(lists.get(i) != null){
                heap.add(lists.get(i));
            }
        }
        ListNode h=new ListNode(0);
        ListNode l=h;
        while(!heap.isEmpty()){
            ListNode head=heap.poll();
            l.next=head;
            l=head;
            if(head.next != null){
                heap.add(head.next);
            }
        }
        return h.next;
}