哈希表的简单介绍

  1. 哈希表在使用层面上可以理解为一种集合结构
  2. 如果只有key，没有伴随数据value，可以使用HashSet结构
  3. 如果既有key，又有伴随数据value，可以使用HashMap结构
  4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
  5. 使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
  6. 放入哈希表的东西（key），如果是基础类型，内部按值传递，内存占用就是这个东西的大小

  7. 放入哈希表的东西（key），如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

    有序表的简单介绍

  8. 有序表在使用层面上可以理解为一种集合结构

  9. 如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)
  10. 如果既有key，又有伴随数据value，可以使用TreeMap结构(C++中叫OrderedMap)
  11. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事5）有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
  12. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
  13. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  14. 放入哈希表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
  15. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

    对于链表如果有换头的操作一定有返回值。

面试时链表解题的方法论

  1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度

  2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

    重要技巧：

  3. 额外数据结构记录（哈希表等）

  4. 快慢指针（例如：一个指针走两步，一个走一步，这个需要根据不同的要求进行改变）

  5. 快指针走两步，慢指针走一步，快指针走到末尾，慢指针来到中间节点。

    判断一个链表是否为回文结构

    【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。
    【例子】1->2->1，返回true；1->2->2->1，返回true；15->6->15，返回true；1->2->3，返回false。
    【例子】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

    1.  // need n extra space
    2.  public static boolean isPalindrome1(Node head) {
    3.      Stack<Node> stack = new Stack<Node>();
    4.      Node cur = head;
    5.      while (cur != null) {
    6.          stack.push(cur);
    7.          cur = cur.next;
    8.      }
    9.      while (head != null) {
    10.          if (head.value != stack.pop().value) {
    11.              return false;
    12.          }
    13.          head = head.next;
    14.      }
    15.      return true;
    16.  }
    18.  // need n/2 extra space
    19.  public static boolean isPalindrome2(Node head) {
    20.      if (head == null || head.next == null) {
    21.          return true;
    22.      }
    23.      Node right = head.next;
    24.      Node cur = head;
    25.      while (cur.next != null && cur.next.next != null) {
    26.          right = right.next;
    27.          cur = cur.next.next;
    28.      }
    29.      Stack<Node> stack = new Stack<Node>();
    30.      while (right != null) {
    31.          stack.push(right);
    32.          right = right.next;
    33.      }
    34.      while (!stack.isEmpty()) {
    35.          if (head.value != stack.pop().value) {
    36.              return false;
    37.          }
    38.          head = head.next;
    39.      }
    40.      return true;
    41.  }
    43.  // need O(1) extra space
    44.  public static boolean isPalindrome3(Node head) {
    45.      if (head == null || head.next == null) {
    46.          return true;
    47.      }
    48.      Node n1 = head;
    49.      Node n2 = head;
    50.      while (n2.next != null && n2.next.next != null) { // find mid node
    51.          n1 = n1.next; // n1 -> mid
    52.          n2 = n2.next.next; // n2 -> end
    53.      }
    54.      n2 = n1.next; // n2 -> right part first node
    55.      n1.next = null; // mid.next -> null
    56.      Node n3 = null;
    57.      while (n2 != null) { // right part convert
    58.          n3 = n2.next; // n3 -> save next node
    59.          n2.next = n1; // next of right node convert
    60.          n1 = n2; // n1 move
    61.          n2 = n3; // n2 move
    62.      }
    63.      n3 = n1; // n3 -> save last node
    64.      n2 = head;// n2 -> left first node
    65.      boolean res = true;
    66.      while (n1 != null && n2 != null) { // check palindrome
    67.          if (n1.value != n2.value) {
    68.              res = false;
    69.              break;
    70.          }
    71.          n1 = n1.next; // left to mid
    72.          n2 = n2.next; // right to mid
    73.      }
    74.      n1 = n3.next;
    75.      n3.next = null;
    76.      while (n1 != null) { // recover list
    77.          n2 = n1.next;
    78.          n1.next = n3;
    79.          n3 = n1;
    80.          n1 = n2;
    81.      }
    82.      return res;
    83.  }

    将单向链表按某值划分成左边小、中间相等、右边大的形式

    【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
    【进阶】在实现原问题功能的基础上增加如下的要求
    【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
    【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
    【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
    【要求】时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

    1.  public static Node listPartition1(Node head, int pivot) {
    2.      if (head == null) {
    3.          return head;
    4.      }
    5.      Node cur = head;
    6.      int i = 0;
    7.      while (cur != null) {
    8.          i++;
    9.          cur = cur.next;
    10.      }
    11.      Node[] nodeArr = new Node[i];
    12.      i = 0;
    13.      cur = head;
    14.      for (i = 0; i != nodeArr.length; i++) {
    15.          nodeArr[i] = cur;
    16.          cur = cur.next;
    17.      }
    18.      arrPartition(nodeArr, pivot);
    19.      for (i = 1; i != nodeArr.length; i++) {
    20.          nodeArr[i - 1].next = nodeArr[i];
    21.      }
    22.      nodeArr[i - 1].next = null;
    23.      return nodeArr[0];
    24.  }
    26.  public static void arrPartition(Node[] nodeArr, int pivot) {
    27.      int small = -1;
    28.      int big = nodeArr.length;
    29.      int index = 0;
    30.      while (index != big) {
    31.          if (nodeArr[index].value < pivot) {
    32.              swap(nodeArr, ++small, index++);
    33.          } else if (nodeArr[index].value == pivot) {
    34.              index++;
    35.          } else {
    36.              swap(nodeArr, --big, index);
    37.          }
    38.      }
    39.  }
    41.  public static void swap(Node[] nodeArr, int a, int b) {
    42.      Node tmp = nodeArr[a];
    43.      nodeArr[a] = nodeArr[b];
    44.      nodeArr[b] = tmp;
    45.  }
    47.  public static Node listPartition2(Node head, int pivot) {
    48.      Node sH = null; // small head
    49.      Node sT = null; // small tail
    50.      Node eH = null; // equal head
    51.      Node eT = null; // equal tail
    52.      Node bH = null; // big head
    53.      Node bT = null; // big tail
    54.      Node next = null; // save next node
    55.      // every node distributed to three lists
    56.      while (head != null) {
    57.          next = head.next;
    58.          head.next = null;
    59.          if (head.value < pivot) {
    60.              if (sH == null) {
    61.                  sH = head;
    62.                  sT = head;
    63.              } else {
    64.                  sT.next = head;
    65.                  sT = head;
    66.              }
    67.          } else if (head.value == pivot) {
    68.              if (eH == null) {
    69.                  eH = head;
    70.                  eT = head;
    71.              } else {
    72.                  eT.next = head;
    73.                  eT = head;
    74.              }
    75.          } else {
    76.              if (bH == null) {
    77.                  bH = head;
    78.                  bT = head;
    79.              } else {
    80.                  bT.next = head;
    81.                  bT = head;
    82.              }
    83.          }
    84.          head = next;
    85.      }
    86.      // small and equal reconnect
    87.      if (sT != null) {
    88.          sT.next = eH;
    89.          eT = eT == null ? sT : eT;
    90.      }
    91.      // all reconnect
    92.      if (eT != null) {
    93.          eT.next = bH;
    94.      }
    95.      return sH != null ? sH : eH != null ? eH : bH;
    96.  }

    复制含有随机指针节点的链表

    【题目】一种特殊的单链表节点类描述如下

    class Node {
 int value;
 Node next;
 Node rand;
 Node(int val) {
     value = val;
 }
}

    rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
    【要求】时间复杂度O(N)，额外空间复杂度O(1)

     public static Node copyListWithRand1(Node head) {
     HashMap<Node, Node> map = new HashMap<Node, Node>();
     Node cur = head;
     while (cur != null) {
         map.put(cur, new Node(cur.value));
         cur = cur.next;
     }
     cur = head;
     while (cur != null) {
         map.get(cur).next = map.get(cur.next);
         map.get(cur).rand = map.get(cur.rand);
         cur = cur.next;
     }
     return map.get(head);
 }

 public static Node copyListWithRand2(Node head) {
     if (head == null) {
         return null;
     }
     Node cur = head;
     Node next = null;
     // copy node and link to every node
     while (cur != null) {
         next = cur.next;
         cur.next = new Node(cur.value);
         cur.next.next = next;
         cur = next;
     }
     cur = head;
     Node curCopy = null;
     // set copy node rand
     while (cur != null) {
         next = cur.next.next;
         curCopy = cur.next;
         curCopy.rand = cur.rand != null ? cur.rand.next : null;
         cur = next;
     }
     Node res = head.next;
     cur = head;
     // split
     while (cur != null) {
         next = cur.next.next;
         curCopy = cur.next;
         cur.next = next;
         curCopy.next = next != null ? next.next : null;
         cur = next;
     }
     return res;
 }

    链表有环无环

    入环节点：进入环的第一个节点

如何判断链表是否有环

用快慢指针，快指针一次走两步，慢指针一次走一步。它们一定会在环上相遇。
相遇之后，快指针回到开始，然后一次走一步，慢指针继续在原位置一次走一步，它们必定在入环结点相遇。

两个单链表相交的一系列问题

【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
image.pngimage.png

public class Code07_FindFirstIntersectNode {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }

    // 找到链表第一个入环节点，如果无环，返回null
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node n1 = head.next; // n1 -> slow
        Node n2 = head.next.next; // n2 -> fast
        while (n1 != n2) {
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        n2 = head; // n2 -> walk again from head
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    // 如果两个链表都无环，返回第一个相交节点，如果不相交，返回null
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) {
            return null;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

    }

}