LinkList Questions

1. 
   Question: Remove Nth Node From End of List QuestionLink
   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.
   Note:
   Given n will always be valid.
   Try to do this in one pass.
   

   
   
   Answer:
   
   

   public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
        val = x;
        next = null;
     }
   }
   
   public ListNode removeNthFromEnd(ListNode head, int n) {
       //use Dummy node to keep list head
       ListNode dummy = new ListNode(0);
       dummy.next = head;
   
       ListNode p = dummy;        
       ListNode q = dummy;
       for(int i=0; i< n+1;i++){   // With n+1(start with dummy node), when q reaches the end of the list, p is at the one before the to-delete node
           q = q.next;
       }
       while(q!=null){
           p = p.next;
           q = q.next;
       }
       p.next =p.next!=null?p.next.next:null;
       return dummy.next;     
   }
   

2. 
   Question: Merge k Sorted Lists QuestionLink
   
   Answer:
   
   Solution#1: merge every two lists into one and recursively finish all lists
   
   
   

   //O(n*k) method: recursively merge two lists (n is total node number)
   public ListNode mergeKLists(ArrayList lists) {
           if(lists==null || lists.isEmpty()) return null;
           if(lists.size()==1) return lists.get(0);
           if(lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
           int count = 2;
           ListNode twoMergeList = mergeTwoLists(lists.get(0), lists.get(1));
           while (count < lists.size()) {
               twoMergeList = mergeTwoLists(twoMergeList, lists.get(count));
               count++;
           }
           return twoMergeList;
   }
   
       //answer of http://oj.leetcode.com/problems/merge-two-sorted-lists/
       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           
           //trick: create a dummy node and use dummyNode's next as newHead
           ListNode dummyNode = new ListNode(0);
           ListNode currNode = dummyNode;
           while(l1!=null||l2!=null) {
               if(l1!=null&&l2!=null) {
                   if(l1.val < l2.val) {
                       currNode.next=l1;
                       l1=l1.next;
                   } else {
                       currNode.next=l2;
                       l2=l2.next;
                   }
               } else if (l1!=null) {
                   currNode.next=l1;
                   l1=l1.next;
               } else {
                   currNode.next=l2;
                   l2=l2.next;
               }
               currNode = currNode.next;
           }
           return dummyNode.next;
       }
   

   Solution#2:

   //use mini-heap to keep the smallest number in k list total listnode in all lists is n, 
       //then time complexity is: O(n*lgk)
       public ListNode mergeKLists2(ArrayList lists) {
       if (lists == null || lists.isEmpty())  return null;
   
       Comparator comparator = new Comparator() {
           @Override
           public int compare(ListNode n1, ListNode n2) {
               if (n1.val < n2.val)  return -1;
               if (n1.val > n2.val)  return 1;
               return 0;
           }
       };
   
       PriorityQueue heap = new PriorityQueue(lists.size(), comparator);
       //O(klogk)
       for (ListNode node : lists) {
           if (node != null)  heap.add(node);
       }
   
       ListNode head=null, cur=null;
       //n
       while (!heap.isEmpty()) {
           if (head == null) {
               head = heap.poll();
               cur = head;
           } else {
               cur.next = heap.poll();
               cur = cur.next;
           }
           if (cur.next != null)  {
              heap.add(cur.next); //heap insert: O(lgk)   
           }
       }
   
       return head;
   }
   

3. 
   Question: Reverse Nodes in k-Group QuestionLink
   
   

   Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
   If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
   You may not alter the values in the nodes, only nodes itself may be changed.
   Only constant memory is allowed.
   For example,
   Given this linked list: 1->2->3->4->5
   
   For k = 2, you should return: 2->1->4->3->5
   
   For k = 3, you should return: 3->2->1->4->5
   

   Answer:
   
   

   public ListNode reverseKGroup(ListNode head, int k) {
           if(head ==null || head.next == null || k<=1) return head;
           ListNode dummy = new ListNode(0);
           dummy.next = head;
           ListNode tail = dummy;
           ListNode kbegin = null;
           ListNode kend = null;
   
           ListNode node = head; //node starts with actual head, not dummy
           int count =0;
           while(node!=null){
               if(count%k==0) { //count starting with 0, recording the kbegin node
                   kbegin = node;
               }
               if(count%k==k-1) { //recording kend node
                   kend = node;
               }
               node = node.next;
               if(count%k==k-1){
                   reverseList(kbegin, kend);
                   tail.next = kend; //link tail head to kend(now beginning node)
                   tail = kbegin; //move tail to the new tail(kbegin)
                   tail.next = node; //kbegin's next was set to null in reverseList, now link to next node in following k
               }
               count++;
           }
           return dummy.next;
       }
       
       public void reverseList(ListNode start, ListNode end) {
           //set end.next=NULL to indicate the end. Don't need this line when actually reversing a list
           end.next = null; 
           ListNode prev = null;
           ListNode curr = start;
           while(curr!=null) {
               ListNode next = curr.next;
               curr.next = prev;
               prev = curr;
               curr = next;
           }
       }
   

4. 
   Question: A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. QuestionLink
   
   Answer:
   
   Solution#1: recursive way. Use a hashmap to save the nodes which are already copied.
   
   

   public RandomListNode copyRandomList(RandomListNode head) {
           Map copiedNodes = new HashMap();
           return copyRandomListHelper(head, copiedNodes);
   }
       
   public RandomListNode copyRandomListHelper(RandomListNode head, Map nodeMap) {
           if(head ==null) return null;
           if(nodeMap.containsKey(head)) return nodeMap.get(head);
           RandomListNode newHead = new RandomListNode(head.label);
           nodeMap.put(head, newHead);
           newHead.next = copyRandomListHelper(head.next, nodeMap);
           newHead.random = copyRandomListHelper(head.random, nodeMap);
           return newHead;
   }
   

   
   
   
   Solution#2: iterative way. Idea from Link.
   Analysis:
   This problem returns a new linked list, which has the same value and structure of the original one. First we can create a new linked list without considering the Random pointer, which is straight forward: Scan every node in the original list and create the new list (line 9- 15 in the code below).
   
   But how to keep the random pointer also correct ? If we only point the new random pointer to the original random pointer, which is not a deep copy (since the deletion of nodes in original list will delete the new one as well). So, how to memorize the relative position of the random node to the current node? Firstly I think to use the length from head node to the random node. For each node, I stored the position of its random node, same position node in the new list is the random node for the node in the new list. This idea can work, but is not efficient. For every node you have to search from the start to the end to find the random, the total complexity is O(n^2). Can we quickly locate the position of the node? Yes! Hash map! A map with the node as key and node as the value can finish the job! We can use the original list node as the key, and the same node in the new list as the value. Now the map[node_old] = node_new, therefore the node_new->random = map[node_old->random]. In this way, the complexity decreases to O(n).
   
   
   

   public RandomListNode iterativeSolution(RandomListNode head) {
            if (head==null) return null;
            Map oldNewMap = new HashMap();
            RandomListNode dummy = new RandomListNode(0);
            RandomListNode newCurr = dummy; //use dummy node as previous node to clone list with only next pointers
            RandomListNode curr = head;
            
            //finish cloning list with next pointers
            while(curr != null) {
                RandomListNode copy = new RandomListNode(curr.label);
                oldNewMap.put(curr, copy);  //key is old node, value is copied node
                newCurr.next = copy;
                curr = curr.next;
                newCurr=newCurr.next;
            }
            
            curr=head;
            newCurr=dummy.next;
            while(curr!=null) {
                if(curr.random == null) {
                    newCurr.random = null;
                } else {
                    newCurr.random = oldNewMap.get(curr.random);
                }
                curr = curr.next;
                newCurr = newCurr.next;
            }
            return dummy.next;
       }