Other

copy list with random pointer

note that, in the first round, we should create the node and put it in the map, and in the second round, establish the next and random relationship.

public RandomListNode copyRandomList(RandomListNode head) {
    if (head == null) return null;

    Map<RandomListNode, RandomListNode> map = new HashMap<>();  // store old-new node pair
    RandomListNode cur = head;

    // create ListNode in the first round
    while (cur != null) {
        RandomListNode node = new RandomListNode(cur.label);
        map.put(cur, node);
        cur = cur.next;
    }

    // create the next & random relation in the second round
    cur = head;
    while (cur != null) {
        RandomListNode node = map.get(cur);
        node.next = map.get(cur.next);
        node.random = map.get(cur.random);

        cur = cur.next;
    }
    return map.get(head);
}

related problems: clone graph

Insertion Sort List

The idea is different from array insertion sort, because we cannot easily locate the previous element.

Given 1 -> 3 -> 2 -> 4 - > null

dummy0 -> 1 -> 3 -> 2 -> 4 - > null
               |    |
              ptr toInsert
-- locate ptr = 3 by (ptr.val > ptr.next.val)
-- locate toInsert = ptr.next

dummy0 -> 1 -> 3 -> 2 -> 4 - > null
          |         |
   toInsertPre     toInsert
-- locate preInsert = 1 by preInsert.next.val > toInsert.val
-- insert toInsert between preInsert and preInsert.next


public ListNode insertionSortList(ListNode ptr) {    
        if (ptr == null || ptr.next == null)
            return ptr;

        ListNode preInsert, toInsert, dummyHead = new ListNode(0);
        dummyHead.next = ptr;

        while (ptr != null && ptr.next != null) {
            if (ptr.val <= ptr.next.val) {
                ptr = ptr.next;
            } else {      
                toInsert = ptr.next;
                // Locate preInsert.
                preInsert = dummyHead;
                while (preInsert.next.val < toInsert.val) {
                    preInsert = preInsert.next;
                }
                ptr.next = toInsert.next;
                // Insert toInsert after preInsert.
                toInsert.next = preInsert.next;
                preInsert.next = toInsert;
            }
        }

        return dummyHead.next;
    }

Plus One Linked List

We can use stack + iteration to solve this problem. But I think this is not what you expect. Ok, how to do that? Recursion.

public ListNode plusOne(ListNode head) {
    if( DFS(head) == 0){
        return head;
    }else{
        ListNode newHead = new ListNode(1);
        newHead.next = head;
        return newHead;
    }
}

public int DFS(ListNode head){
    if(head == null) return 1;

    int carry = DFS(head.next);

    if(carry == 0) return 0;

    int val = head.val + 1;
    head.val = val%10;
    return val/10;
}

What is the advantage of Recursion? more efficient. O(n) time , O(n) space.

Lintcode:

Convert a binary tree to a circular doubly link list