[LeetCode]Copy List with Random Pointer

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.

解题思路：
这题还是挺巧妙的。由于每个node有一个指向随机结点的指针，而要找到此随机结点事很困难的。如果按照传统思路，新旧linkedlist分别为两个独立的linkedlist, 那对于新的linkedlist中的每个node来说，我们只知道对应的node在原来的linkedlist里指向的random 的node. 这是非常困难的，这的记住每个random node 在linkedlist 中的index, 这是非常复杂的。
所以，如果我们想到将新的node放到原来的linkedlist里，然后每个新的node都在对应旧的node的后面一位，那么我们就能很容易的找到新的random node了。因为每个新点的random node就是旧点的random node 的下一位。
总结下来，我们有三步：

1. copy the node
2. copy the random pointer
3. decouple the new linkedlist

Java Code:

public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode safehead = new RandomListNode(0);
           RandomListNode currP = head;
           
           //copy the node
           while(currP != null){
               RandomListNode tmp = new RandomListNode(currP.label);
               tmp.next = currP.next;
               currP.next = tmp;
               currP = tmp.next;
           }
           
           currP = head;
           //copy the random pointer
           while(currP != null){
               
               if(currP.random != null){
                  currP.next.random = currP.random.next;    
               }
               
               currP = currP.next.next;
           }
           
           //decouple the list
            RandomListNode p = safehead;
            currP = head;
            
            while(currP != null){
                p.next = currP.next;
                currP.next = currP.next.next;
                currP = currP.next;
                 p = p.next;
            }
           
            return safehead.next;
    }

[LeetCode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解题思路： 因为n可能会大于list的总长度，所以我们先遍历整个list，然后将tail指向head,组成一个圈，然后再走num - n%num步，就将圈解开即可。
最开始自己是一遍一遍的遍历list。看了水中的鱼的讲解，觉得很赞。

Java Code:

public ListNode rotateRight(ListNode head, int n) {
        if(head == null || n == 0) return head;
        
        ListNode p = head;
        
        int count = 1;
        while(p.next != null){
             count++;
             p = p.next;
        }
        
        if(n%count == 0) return head;
        
       p.next = head;
       int i = 0;
        
       while( i < count - n%count){
           i++;
           p = p.next;
       }
       
       ListNode newhead = p.next;
       p.next = null;
       
       return newhead;
    }

[LeetCode] Reverse Linked List

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

解题思路：
 1. reverse linkedlist，通常需要2个指针和一个temp 指针。这里最后要将reversedlist和原来的list链接起来，所以我们还需要一个指针来存储m-1的node。
2. 这里会考虑到m == 1的情况，所以我们加一个dummy node
 
Java Code:

 public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode p = head;
        ListNode safehead = new ListNode(0);
        safehead.next = head;
        ListNode prevM = safehead;
        ListNode prev = null;
         
        int i = 1;
        
        while( p != null && i <= n){
            if(i >= m){
               ListNode tmp = p;
               p = p.next;
               tmp.next = prev;
               prev = tmp;
            }else{
              prevM = prevM.next;
              p = p.next;
            }
            i++;
        }
       
        prevM.next.next = p;
        prevM.next = prev;
        
        return safehead.next;
    }

[LeetCode] Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

解题思路：
1，找出中间位置的element，将linkedlist分为两半
2，反转后半部分的linkedlist
3，将2部分的linkedlist合成

注意：在找出median的element的时候，我用了最基本的方法，统计出element的总数，然后count/2. 这样就会重复遍历list. 可以设置2个指针，一个每次走一步，另一个每次走2步，走到2步为null的时候，走一步的指针就指向的为中间的element


Java Code:

public void reorderList(ListNode head) {
        int count = 0;
        ListNode p = head;
        
        while( p != null){
            p = p.next;
            count++;
        }
        
        if(count < 3) return;
        
        //find the median element starting with p
        ListNode prev = head;
        p = head;
        int i = 0;
        while( p != null && i <= count/2){
            i++;
            prev = p;
            p = p.next;
        }
        
        //reverse the after half linkedList
        prev.next = null;
        prev = prev.next;
        
        while(p != null){
               ListNode tmp = p;
               p = p.next;
               tmp.next = prev;
               prev = tmp;
        }
        
        p = prev;
        prev = head;
        //merge the two half linkedlist 
        while(p != null && prev != null){
            ListNode tmp = p;
            p = p.next;
            tmp.next = prev.next;
            prev.next = tmp;
            prev = tmp.next;
        }
        
    }

[LeetCode] Linked List Cycle 2

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

解题思路：
1. 延续linked list cycle1的题目，先用两个指针p, pn分别走一步和2步，则它们相遇的时候，等于
    n = m*Y  (Y为圈的长度，n为移动一位走的步数)
   如果假设它们相遇的位置离圈开始的那个地方为k，则有，x + k ＝ n (x 为非圈的点数)。
   也就是说 x + k = m*Y. 也就是p再往后走x步就到达了圈开始的结点。

如果此时我们再从头开始一个指针一起往后走，则走x步，它们会在圈开始的结点处相遇

Java Code

 ListNode p = head;
        ListNode pn = head;
        
        while(p != null && pn != null && pn.next != null){
            p = p.next;
            pn = pn.next.next;
            
            if(p != null && p == pn){
                ListNode pre = head;//set another pointer to the beginning
                
                while(p != pre){
                    p = p.next;
                    pre = pre.next;
                }
                return pre;
            }
        }
        
        return null;

[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

解题思路：
1. 需要2个指针，一个是遍历List，指向将要插入的节点，另外一个是遍历已经sorted的部分，找到要插入的位置
2. 在List的头，加入一个dummy node, 因为新插入的节点可能会在头部

public ListNode insertionSortList(ListNode head) {
        ListNode res = new ListNode(0);        
        ListNode pNode = head;
   
        while(pNode != null){
              ListNode tNode = res;
              
              while( tNode.next != null  && pNode.val > tNode.next.val){
                  tNode = tNode.next;
              }
              
              ListNode tNextNode = tNode.next;
              tNode.next = pNode;
              pNode = pNode.next;
              tNode.next.next = tNextNode;
        }
        
        return res.next;
    }

[LeetCode] Add Two Numbers

Question:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解题思路： 一道实现题

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           ListNode p1 = l1;
           ListNode p2 = l2;
           ListNode head = new ListNode(0);
           ListNode p = head;
           
           int add = 0;
           
           while(p1 != null || p2 != null || add > 0){
               int add1 = 0, add2 = 0;
               
               if(p1 != null){
                  add1 = p1.val;
                  p1 = p1.next;
               } 
               
               if(p2 != null){
                   add2 = p2.val;
                   p2 = p2.next;
               } 
               
                int val = (add1 + add2 + add)%10;
                add = (add1 + add2 + add)/10;
                
                ListNode l = new ListNode(val);
                p.next = l;
                p = p.next;
           }
           
           return head.next;
    }