Reverse Linked List

Reverse a singly linked list.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Naive Thinking: At first, I thought it cannot be done in O(1) space, so I use a stack and go through the linked-list once pushing one by one into stack. And then pop from the stack one by one. Not surprisingly, I got memory limit exceed. That's probably a sign that I used extra space. So I begin to think about using O(1) space. Just pointing each Node's next pointer to its previous one. In such a process, I need to always note down its next Node first or I will lost the remaining Nodes.

Iteratively:

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   // iteratively  
   public ListNode reverseList(ListNode head) {  
     ListNode pre = null, cur = head, next = null;  
     while(cur!=null){  
       next = cur.next;  
       cur.next = pre;  
       pre = cur;  
       cur = next;  
     }  
     return pre;  
   }  
 }  

Recursively:

 public class Solution {  
   // recursively  
   public ListNode reverseList(ListNode head) {  
     return reverseList(null, head);  
   }  
   private ListNode reverseList(ListNode pre, ListNode cur){  
     // ending case  
     if(cur==null) return pre;  
     // general case  
     ListNode next = cur.next;  
     cur.next = pre;  
     return reverseList(cur, next);  
   }  
 }  

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5


Naive Way: It is the most common way of manipulating linked list. But as for linked list, null pointer will always be a problem.

As usual, I use a fake head pointer to make my code more smooth.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public ListNode removeElements(ListNode head, int val) {  
     ListNode fake = new ListNode(0);  
     ListNode pre = fake;  
     fake.next = head;  
     while(pre.next!=null){  
       ListNode cur = pre.next;  
       if(cur.val==val)  
         pre.next = cur.next; // remove the node  
       else  
         pre = cur;  
     }  
     return fake.next;  
   }  
 }  

Remove Nth Node From End of List

Given a linked list, remove the n^th 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.

Naive Way: Keep two pointers, let the second pointer move n step first. Then the gap between two pointers is n. Keep moving both pointers forward at same speed until second one reach the end. Then reconnect.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode removeNthFromEnd(ListNode head, int n) {  
     ListNode fake = new ListNode(0);  
     fake.next = head;  
     ListNode first = fake, second = fake;  
     // forward second by n  
     while(n-->0 && second.next!=null) second = second.next;  
     // edge case, length of linkedlist< n  
     if(n > 0){return head;}  
     // forward first and second till second reach the end  
     while(second.next!=null){  
       first = first.next;  
       second = second.next;  
     }  
     ListNode temp = first.next.next;  
     first.next = temp;  
     return fake.next;  
   }  
 }  

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.

Naive Way: A usual way is to treat it like merging two sorted arrays.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     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;  
     }  
     if(l1 != null) cur.next = l1;  
     if(l2 != null) cur.next = l2;  
     return fake.next;  
   }  
 }  

Improved way: There is a better to make use a queue structured recursive method.

 public class Solution {  
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
     if(l1==null) return l2;  
     else if (l2==null) return l1;  
     if(l1.val < l2.val){  
       l1.next = mergeTwoLists(l1.next, l2);  
       return l1;  
     }else{  
       l2.next = mergeTwoLists(l1, l2.next);  
       return l2;  
     }  
   }  
 }  

Merge k Sorted Lists

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

Naive Way:This question is asked on My Algorithm Course Mid-term Exam. Unfortunately, I didn't work thought it. But now, I know two methods to this question in O(nlogk) run time.

The first method is keep a heap. Push the head of each list into the heap. Pop the min from the heap and push its next into the heap. This method is an ideal way to solve the problem.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     Comparator<ListNode> c = new Comparator<ListNode>(){  
       @Override  
       public int compare(ListNode a, ListNode b){  
         if(a.val > b.val) return 1;  
         else if(a.val < b.val) return -1;  
         else return 0;  
       }  
     };  
     PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), c);  
     // initialize heap  
     for(int i = 0;i < lists.size();i++) if(lists.get(i)!=null) heap.offer(lists.get(i));  
     // pop from heap until empty  
     while(!heap.isEmpty()){  
       cur.next = heap.poll();  
       cur = cur.next;  
       if(cur.next!=null) heap.offer(cur.next);  
     }  
     return fake.next;  
   }  
 }  

Another way is great, too. Keep merge the lists two by two until there is only one list. And for merge two lists, I can use former way in Merge Two Sorted Lists.

 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     for(int i = 1;i < lists.size();i*=2)  
       for(int j = 0;j+i < lists.size();j+=2*i)  
         lists.set(j,mergeTwoSortedLists(lists.get(j), lists.get(j+i)));  
     return lists.get(0);  
   }  
   private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2){  
     if(l1==null) return l2;  
     else if (l2==null) return l1;  
     if(l1.val < l2.val){  
       l1.next = mergeTwoSortedLists(l1.next, l2);  
       return l1;  
     }else{  
       l2.next = mergeTwoSortedLists(l1, l2.next);  
       return l2;  
     }  
   }  
 }  

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Naive Way: A straightforward way is to use two head pointers to carry the list with all nodes less than x and the list with all nodes greater or equal to x. And that's O(1) space. Reset the tail of the second list may be ignored!

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     ListNode less = new ListNode(0);  
     ListNode noLess = new ListNode(0);  
     ListNode p1 = less;  
     ListNode p2 = noLess;  
     for(ListNode cur = head;cur!=null;cur = cur.next){  
       if(cur.val < x){  
         p1.next = cur;  
         p1 = p1.next;  
       }else{  
         p2.next = cur;  
         p2 = p2.next;  
       }  
     }  
     p2.next = null;  
     p1.next = noLess.next;  
     return less.next;  
   }  
 }  

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Naive Way:时间复杂度的要求决定了只能是merge sort, quick sort 或者用 heap。空间复杂度先排除heap。Quick sort不熟，先试merge sort。merge sort能否只用O(1) space？好像是可以的。

写了N久终于写完了。用一快一慢两个指针引领要被merge的部分，merge函数需要在末尾清零（null），主函数需要用一个指针标记剩下的部分，以便前面部分merge完以后接上。

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode sortList(ListNode head) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake, fast = fake, slow = fake;  
     fake.next = head;  
     // get the length of list  
     int length = 0;  
     while(cur.next!=null){  
       length++;  
       cur = cur.next;  
     }  
     for(int step = 1;step < length;step*=2){  
       cur = fake;  
       while(cur.next!=null){  
         slow = cur.next;  
         fast = cur.next;  
         int i = 0;  
         // find correct merge starting position  
         while(fast.next!=null && i < step){fast = fast.next; i++;}  
         if(i!=step) break;  
         ListNode temp = fast;  
         i = 0;  
         while(temp!=null && i < step){temp = temp.next; i++;}  
         // merge two lists  
         cur.next = merge(slow, fast, step);  
         // connect with remaining nodes  
         i = 0;  
         while(i < 2*step && cur.next!=null){cur = cur.next;i++;}  
         cur.next = temp;  
       }  
     }  
     return fake.next;  
   }  
   private ListNode merge(ListNode a, ListNode b, int len){  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     int i = 0,j = 0;  
     while(i < len && j < len && a!=null && b!=null){  
       if(a.val < b.val){  
         cur.next = a;  
         a = a.next;  
         i++;  
       }else{  
         cur.next = b;  
         b = b.next;  
         j++;  
       }  
       cur = cur.next;  
     }  
     while(i < len && a!=null){  
       cur.next = a;  
       a = a.next;  
       i++;  
       cur = cur.next;  
     }  
     while(j < len && b!=null){  
       cur.next = b;  
       b = b.next;  
       j++;  
       cur = cur.next;  
     }  
     cur.next = null;  
     return fake.next;  
   }  
 }  

Improved Way:看到Discuss里很多人都是 大的merge  call 小的merge，那样就会造成一个stack的空间使用，就不是O(1)的了，要实现O(1)，必须从小的往大的写，这样才不会同时进行多个merge。

一些提升的地方：

有一个人用Bit 运算移位来实现step*2，这样挺好的。

有一个人将获取slow, 和fast的位置写成单独的函数，这样主函数就会清晰很多。

最重要的问题：Quick Sort 是否可以写成O(1)的关于链表的。从算法的流程上讲是可以的，先对整个list 进行左右交换，然后对前一半和后一半分别进行左右交换，这样下来应该可以不适用额外空间。

Reverse Nodes in k-Group

Reverse Nodes in k-Group

 

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 

 

Naive Way: 如何reverse Linked List。是护住最后一个节点，不断的往后insert节点，那么reverse k 个也是一样的。护住的可以是起点也可以是终点，但这道题要求最后不够k 个保持原样，护住起点不能够有效将最后多出部分写入大循环，护住终点的方法则可以先判断是否找到终点来对付这种情况。

 

算法复杂度O(n), space O(1)。第一次将节点插入终点后面的时候，我记下了新的起点的位置，这样就不用再完成k个再遍历至那里。

  /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode reverseKGroup(ListNode head, int k) {  
     ListNode fakeHead = new ListNode(0);  
     ListNode cur = fakeHead, tail = cur;  
     fakeHead.next = head;  
     int i = 0;  
     while(tail!=null){  
       for(i = 0;i < k && tail.next!=null;i++)  
         tail = tail.next;  
       if(i<k) return fakeHead.next;  
       ListNode nextCur = null;  
       while(cur.next!=tail){  
         ListNode temp = cur.next;  
         if(nextCur==null) nextCur = temp;  
         cur.next = temp.next;  
         temp.next = tail.next;  
         tail.next = temp;  
       }  
       cur = nextCur;  
       tail = cur;  
     }  
     return fakeHead.next;  
   }  
 }  

 

 

 

Improved Way: 在Discuss里还有一种recursive的方法，就是将翻转k个写进一个子函数，每次调用后把它接起来，觉得O(1) space 还是不适合recursive。

Add Two Numbers

Add Two Numbers

 

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

Naive Way: 审题：1.non-negative numbers 2. stored in reverse order 3. linked-list
使用两个指针遍历两个链表。

算法复杂度是O(n)， space O(1)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head1 = new ListNode(0);
        ListNode head2 = new ListNode(0);
        boolean carry = false;
        head1.next = l1;
        head2.next = l2;
        l1 = head1;
        l2 = head2;
        while(l1.next!=null && l2.next!=null){
            l1 = l1.next;
            l2 = l2.next;
            l1.val += l2.val+(carry?1:0);
            carry = l1.val>9;
            l1.val = l1.val%10;
        }
        while(l2.next!=null){
            l2 = l2.next;
            l2.val += carry?1:0;
            carry = l2.val>9;
            l2.val = l2.val%10;
            l1.next = l2;
            l1 = l1.next;
        }
        while(l1.next!=null){
            l1 = l1.next;
            l1.val+= carry?1:0;
            carry = l1.val >9;
            l1.val = l1.val%10;
        }
        if(carry){
            ListNode tail = new ListNode(1);
            l1.next = tail;
        }
        return head1.next;
    }
}


可以用一个循环完成。还可以把carry也写进去，但是觉得把carry单独写清楚些。

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode pre = head;
        ListNode cur = pre;
        head.next = l1==null?l2:l1;
        boolean carry = false;
        while(l1!=null || l2!=null){
            int val = (l1==null?0:l1.val)+(l2==null?0:l2.val)+(carry?1:0);
            carry = val > 9;
            val %= 10;
            cur = l1==null?l2:l1;
            cur.val = val;
            
            pre.next = cur;
            pre = cur;
            l1 = l1==null?l1:l1.next;
            l2 = l2==null?l2:l2.next;
        }
        if(carry){
            ListNode tail = new ListNode(1);
            pre.next = tail;
        }
        return head.next;
    }
}

还可以是recursive的，但是需要O(n)的space。这里意外的法相虽然recursive的要用O(n)的space，但是用时还是比iterative的少得多。标记一下，看以后的题目是不是这样的。

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        return addTwoNumbers(l1,l2,head,false);
    }
    
    private ListNode addTwoNumbers(ListNode t1, ListNode t2, ListNode pre, boolean carry){
        // base case
        if(t1==null && t2==null)
            return carry?new ListNode(1):null;
        // recursive
        ListNode cur = t1==null?t2:t1;
        cur.val = (t1==null?0:t1.val)+(t2==null?0:t2.val)+(carry?1:0);
        carry = cur.val > 9;
        cur.val %= 10;
        pre.next = cur;
        cur.next = addTwoNumbers(t1==null?t1:t1.next, t2==null?t2:t2.next, cur, carry);
        return cur;
    }
    
}

Reverse Linked List II

Reverse Linked List II (Upgrade Version for Rotate 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.


Naive Way:一开始想了一个不断交换的方法，这样可以做到in-place,但是交换之后最大的麻烦就是无法在O(1)的时间找回远端的节点的父节点，所以这个方法不符合O(n)的复杂度。然后才想到了这个不断插入的做法。现将远端的指针和近端指针摆好，不断将近端指针指向的插入远端指针后面，直到近端指向远端指针。也可以不断将近端后面的指针插入近端前面，知道近端和远端相遇。

算法复杂度是O(n), space O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode p1 = newHead, p2 = p1;
        int i = 0;
        while(++i <= n && p2.next!=null){
            if(i < m) p1 = p1.next;
            p2 = p2.next;
        }
        // since n <= length of list, no need to check i<n
        while(p1.next!=p2){
            ListNode temp = p1.next;
            p1.next = temp.next;
            
            temp.next = p2.next;
            p2.next = temp;
        }
        return newHead.next;
    }
}

Swap Nodes in Pairs

Swap Nodes in Pairs

 

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Naive Way:如果要交换两个指针，必须要知道他们的父指针而非本身。可以使用两个指针，一个每回跳两次，一个每回跳一次，交换他们的子节点。

使用constant space。并且使用了一个额外的头结点方便记录返回值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode p1 = newHead, p2 = p1;
        while(p2.next!=null){
            p2 = p2.next;
            if(p2.next==null) break;
            p2 = p2.next;
            // switch
            ListNode temp = p1.next;
            p1.next = p2;
            temp.next = p2.next;
            p2.next = temp;
            
            p1 = temp;
            p2 = temp;
        }
        return newHead.next;
    }
}

 

Insertion Sort List

Insertion Sort List

 

Sort a linked list using insertion sort.

 

Naive Way:Insertion Sort是和Bubble Sort类似的一种，不断将元素插入到已排好序的序列中的排序算法 。那么一开始排好序的就只有head一个节点，然后将后面的节点不断的插入到排好序的节点中。

 

算法复杂度必须是O(n^2)，space O(1)。得注意待插入的节点的next指针要先清理掉，否则后面一整串跟着带进来了。

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        ListNode pre = cur;
        while(cur!=null){
            pre = cur;
            cur = cur.next;
            pre.next = null;
            insert(newHead, pre);
        }
        return newHead.next;
    }
    
    private void insert(ListNode head, ListNode node){
        if(node==null){return;}
        ListNode pre = head;
        ListNode cur = pre;
        boolean found = false;
        while(cur.next!=null){
            pre = cur;
            cur = cur.next;
            if(cur.val > node.val){
                node.next = cur;
                pre.next = node;
                found = true;
                break;
            }
        }
        if(!found)
            cur.next = node;
    }
}

 

 

Clone Graph

Clone Graph

 

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

Naive Way:难点在于穿件了新的节点如何找回原来对应的节点，并且输入只有一个节点。

用Map可以正中下怀的解决这个问题。

算法复杂度是O(n),space是O(n)。 

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

public class Solution {

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

        Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();

        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();

        if(node==null){return null;}

        // BFS, give every node a clone, put relationship into a map

        UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);

        map.put(node,newHead);

        queue.add(node);

        while(!queue.isEmpty()){

            UndirectedGraphNode temp = queue.poll();

            for(int i = 0;i < temp.neighbors.size();i++){

                if(!map.containsKey(temp.neighbors.get(i))){

                    queue.add(temp.neighbors.get(i));

                    UndirectedGraphNode newNode = new UndirectedGraphNode(temp.neighbors.get(i).label);

                    map.put(temp.neighbors.get(i),newNode);

                }

            }

        }

        // according to the map, construct new graph

        queue.add(node);

        set.add(node);

        while(!queue.isEmpty()){

            UndirectedGraphNode temp = queue.poll();

            if(!map.containsKey(temp)){return null;}

            UndirectedGraphNode clone = map.get(temp);

            for(int i = 0;i < temp.neighbors.size();i++){

                if(!map.containsKey(temp.neighbors.get(i))){return null;}

                clone.neighbors.add(map.get(temp.neighbors.get(i)));

                if(!set.contains(temp.neighbors.get(i))){

                    set.add(temp.neighbors.get(i));

                    queue.add(temp.neighbors.get(i));

                }

            }

        }

        return map.containsKey(node)?map.get(node):null;

    }

}

 

Improves Way: 后来，我根据Copy list with random pointer里看别人的一个算法，想到可以套用过来，在每隔节点的最后增加一个新的neighbor，然后将每个节点的最后一个neighbor指向他所有neighbor的最后一个neighbor。

 

这样子不需要额外的空间存关系，但是遍历的原因还是要O(n)的space。

 

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null){return null;}
       
        // create a new Node with the same label put it as the last neighbor for the original node
        ArrayList<Integer> table = new ArrayList<Integer>();
        UndirectedGraphNode cur = node;
        UndirectedGraphNode rslt = null;
        Stack<UndirectedGraphNode> s = new Stack<UndirectedGraphNode>();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                for(int i = 0;i < cur.neighbors.size();i++){
                    if(!table.contains(cur.neighbors.get(i).label)){
                        s.push(cur.neighbors.get(i));
                    }
                }
                UndirectedGraphNode newNode = new UndirectedGraphNode(cur.label);
                cur.neighbors.add(newNode);
            }
        }
       
        // assign relationship for the new nodes
        UndirectedGraphNode temp = null;
        table.clear();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                for(int i = 0;i < cur.neighbors.size()-1;i++){
                    temp = cur.neighbors.get(i);
                    cur.neighbors.get(cur.neighbors.size()-1).neighbors.add(temp.neighbors.get(temp.neighbors.size()-1));
                    s.push(temp);
                }
            }
        }
       
        rslt = node.neighbors.get(node.neighbors.size()-1);
       
        // delete the relationship between original nodes and new nodes
        table.clear();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                cur.neighbors.remove(cur.neighbors.size() - 1);
                for(int i = 0;i < cur.neighbors.size();i++){
                    s.push(cur.neighbors.get(i));
                }
            }
        }
       
        return rslt;
    }
 

 

Rotate List

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.

Naive Way: 这里联想到了找链表的中点的方法 （龟兔赛跑的启示）。两个指针，如果一个指针一次走一步，一个指针一次走两步，一直走知道某一个遇到null, 走的慢的指针就会正好走到链表的中点。这里也可以用。先把第二个指针走出k步，然后两个指针同时往前走，第二个指针遇到null的时候，第一个指针正好走到我们想要做为新head的地方，再把原来的头接到第二个指针的尾部。

这里我自己做这种指针链表的题目喜欢新设一个头，相当于增加了一个-1的位置，可以避免head=null单独写，正常步数循环的情况会获得父节点instead of子节点，感觉这样方便点。

实际做的时候发现循环到头会自动从head开始继续循环数，所以添加让兔子自动从尾部找到头部的条件。这也是自己没读懂题意。

算法复杂度是O(max(l,n))

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode hare = newHead;
        ListNode tortoise = hare;
        int i = 0;
        while(i < n){
            if(hare.next==null)
                hare = newHead;
            hare = hare.next;
            i++;
        }
        if(hare==tortoise){return newHead.next;}
        while(hare!=null && hare.next!=null){
            tortoise = tortoise.next;
            hare = hare.next;
        }
        if(tortoise!=newHead){
            newHead.next = tortoise.next;
            hare.next = head;
            tortoise.next=null;
        }
        return newHead.next;
    }
}


Improved Way: 由于运行时间排的很靠后，有必要思考一下这样的做法是不是好了。如果不需要把头尾相接似乎很方便，那是不是先令n = n%l （l为链表长度)呢？这样试了试。居然运行时间提高了很多。但方法没变化的。

算法复杂度是O(min(l,n))

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode hare = newHead;
        ListNode tortoise = hare;
        int i = 0,length = 0;
        while(hare.next!=null){
            hare = hare.next;
            length++;
        }
        hare = tortoise;
        while(i < (length==0?0:n%length)){
            hare = hare.next;
            i++;
        }
        if(hare==tortoise){return newHead.next;}
        while(hare!=null && hare.next!=null){
            tortoise = tortoise.next;
            hare = hare.next;
        }
        if(tortoise!=newHead){
            newHead.next = tortoise.next;
            hare.next = head;
            tortoise.next=null;
        }
        return newHead.next;
    }
}


后来在discuss上又看到一个比较好的点子，先把链表连成一个圈，然后循环跳步，最后再断开。但实际运行起来发现是完全一样的，只不过连成圈将 n > length的情况包括进去，和我的第一种方法是一样的。

Intersection of Two Linked Lists

Intersection of Two Linked Lists

 

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Naive Way: 对每一A node, 遍历一遍B node,看是否交汇。这样的算法复杂度是O(n^2)。
但是题目要求了O(n) ，说明就一定存在O(n)的解法。链表有一个重要的特性就是有指针。
这些指针可以被灵活使用，这里让我想起了Populating Next Right Pointers in Each Node II里那个把next指针指向父节点的人，当时这个做法一下子直接打破了常规的想法，让指针不再局限于它的名字，我们其实也可以将left 和 right指向父节点什么的，这种约定俗成的变量名造成了先入为主的思维，往往会限制我们的想法。

那么看来要实现O(n)就必须利用好这些指针了，但是这道题不同于树，每一个节点只有一个指针，如果我们改变某一个指针，就断掉了，就无法修复了。所以我们不能断掉这些指针，但仍可以在不断掉整个链的情况下改变这些指针。

一开始我的想法是交叉A 链表和B链表的指针，看能不能弄出些名堂，但是无论怎么交叉，都只是将A和B前面的部分增长变短，问题就变成了对一个长度不同的A,B链表求交汇点。所以这样的尝试是失败的。

其实有一个节点的指针是一直没有用的，就是最后一个节点的指针，连接它到任意一个位置都改变了整个链表的结构，没错，增加了一个圈。这时才发现题目中的Notes是在给提示，前面有做过用龟兔赛跑的办法求圈的起始位置的题目，这里就可以用上了。当把尾部节点的指针链接至任意一个链表的开头，就变成一个含圈链表求圈起始位置的题目。而龟兔赛跑的算法复杂度正好是O(n)。具体龟兔赛跑是怎么回事，这里有一个比较好的教程Detecting a Loop in Singly Linked List - Tortoise & Hare

这道题是自己想出来的，还是比较开心。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // edge case
        if(headA == null || headB == null){return null;}
        // connect list A into a circle
        ListNode temp = headA;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = headA;
        // find the start node of the circle
        ListNode hare = headB;
        ListNode tortoise = headB;
        while(true){
            // hare step 2 forward
            if(hare.next != null){
                hare = hare.next;
                if(hare.next != null){
                    hare = hare.next;
                }else{
                    temp.next = null;
                    return null;
                }
            }else{
                temp.next = null;
                return null;
            }
            // tortoise step 1 forward
            if(tortoise.next != null){
                tortoise = tortoise.next;
            }else{
                temp.next = null;
                return null;
            }
            // check if they meet
            if(hare == tortoise){
                break;
            }
        }
        hare = headB;
        while(hare != tortoise){
            hare = hare.next;
            tortoise = tortoise.next;
        }
        // break list A into singly list
        temp.next = null;
       
        return hare;
    }
}

 

 

 

Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node

 

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL 

Naive Way: 这里有一个重要限制是constant space.所以不能用stack或者queue来进行遍历。

这里有个问题困扰了我，如何在不用extra space的前提下遍历一颗无父指针二叉树呢。答案是不可能的！

因为二叉树有两个分支，无论先遍历哪一边分支，都必须要记下兄弟节点，否则一旦往下走就不能回头。

而且光记录一个兄弟节点还不行，必须把同一层的兄弟节点都记录下来，这样是和BFS，DFS相对应的O(n)

space。

明白这一点很重要，说明这道题在坑人。

终于过了好久，我发现这道题的next指针导致了我们可以用constant space去遍历一整棵树。 

因为如果我们知道next指针，就可以通过父节点的next指针访问到同一层的兄弟节点。也就是说，

我们不仅要连起这些next指针，还要利用之前连好的这些next指针方便我们连下一层的next指针。

简单的逻辑描述为：

如果一个节点为左节点，其next为父亲的右节点。

如果一个节点为右节点，其next为父亲节点的next节点的左节点（如果有的话）。

并且由于next指针是从左指向右的，我觉得应该从左往右进行遍历。通过next获得下一个要

处理的节点。

写点有点别扭，用了一个do-while语句。但是思想应该是对的。一层一层来，从左到右，

每一层都要记下最左边的子节点，作为下一层遍历的开头。

/**

 * Definition for binary tree with next pointer.

 * public class TreeLinkNode {

 *     int val;

 *     TreeLinkNode left, right, next;

 *     TreeLinkNode(int x) { val = x; }

 * }

 */

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }
}

 

Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

 

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL 

Naive Way:这次多了一个不满秩的条件，很明显的意图是要看能否通过修改第一次的代码得到。

第一次的代码：

public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }

我想基本结构应该是不变，但是现在左子节点和右子节点都可能不存在。分析一下不存在的时候该怎么办：

1.如果左子节点不存在，最左边的节点就应该是右节点。

2.如果右子节点不存在，next该指向的是父节点的next节点的左子节点。

很棒，这两点是相互作用的.对于找最左子节点和右节点分别写了对应函数，发现二者仅一处不同。

private TreeLinkNode searchLeft(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.left!=null)
            return node.left;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

private TreeLinkNode searchRight(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

替换相应部分的结果为：

（这里结束条件需要略作改动，因为不能再用是否满秩作为判断条件。后来想想，应该第一个也这样写的） 

public void connect(TreeLinkNode root) {

       if(root==null)

           return;

       TreeLinkNode leftMost = root;

       TreeLinkNode node = null;

       while(leftMost!=null){

           node = leftMost;

           leftMost = searchLeft(node);

           do{
              if(node.left!=null)

                   node.left.next = searchRight(node);

               if(node.right!=null)

                   node.right.next = searchLeft(node.next);

               node = node.next;

           }while(node!=null);

       }

   } 

Improved Way: 这样是否就已经可以了呢。我在discuss中看到一个很有意思的想法。有个人先把搜友节点的next节点指向父节点，然后展开BFS把next pointer指向下一个。感觉和我的思路是一样的，都是要先把上一层的next连好，记下下一层最左边的，然后通过上一层的next找同层的兄弟节点。但是把next指向父节点就有了无限可能性，因为可以no extra space从下往上遍历节点了。

以下代码是leetcode用户 pavan.singitham的。

public class Solution {
public void connect(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    root.next = null;
    pointChildrenToParents(root);
    rotateNextClockwise(root);
}

// point each child's next pointer to the parent
private void pointChildrenToParents(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    if(root.left != null) {
        root.left.next = root;
        pointChildrenToParents(root.left);
    }
    if(root.right != null) {
        root.right.next = root;
        pointChildrenToParents(root.right);
    }
}

// now update the next pointer 1-level at a time to point to the next node in that level
private void rotateNextClockwise(TreeLinkNode root) {
    if(root == null) {
        return;
    }

    TreeLinkNode firstNodeInNextLevel = null; // save first node in next level for bfs
    while(root != null) {
        if(firstNodeInNextLevel == null) {
            firstNodeInNextLevel = (root.left != null)? root.left : root.right;
        }
        if(root.right != null) {
            if(root.left != null) {
                root.left.next = root.right;
            }
            root.right.next = findNextChild(root.next);
            root = (root.right.next != null) ? root.right.next.next: null;
        }
        else if(root.left != null) {
            root.left.next = findNextChild(root.next);
            root = (root.left.next != null) ? root.left.next.next: null;
        }
        else {
            root = root.next;
        }
    }

    rotateNextClockwise(firstNodeInNextLevel);
}

// traverse next chain till we find a child for current level
private TreeLinkNode findNextChild(TreeLinkNode root) {
    for(TreeLinkNode tmp = root; tmp != null; tmp = tmp.next) {
        if(tmp.left != null) {
            return tmp.left;
        }
        else if(tmp.right != null) {
            return tmp.right;
        }
    }
    return null;
} 

} 

看到一个更好的代码，思路是一样的，带式代码质量好很多。来自leetcode的 davidtan1890用户。

public void connect(TreeLinkNode root) {

        while(root != null){
            TreeLinkNode tempChild = new TreeLinkNode(0);
            TreeLinkNode currentChild = tempChild;
            while(root!=null){
                if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
                if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
                root = root.next;
            }
            root = tempChild.next;
        }
    }